Seminar4

// ============================================================================================
// biginteger.h

#pragma once

#include <iostream>
#include <string>
#include <vector>

class BigIntegerOld {
 public:
  void SetValue(long long value);
  long long Value() const { return value_; }

 private:
  long long value_ = 0;

};

BigIntegerOld CreateVeryBigInteger();

typedef unsigned int uint;

class BigInteger {
 public:
  std::string ToString() const;
  BigInteger operator+(const BigInteger& second) const;
  BigInteger operator-(const BigInteger& second) const;
  BigInteger operator*(const BigInteger& second) const;
  BigInteger operator/(const BigInteger& second) const;
  BigInteger operator%(const BigInteger& second) const;

  BigInteger& operator+=(const BigInteger& second);
  BigInteger& operator-=(const BigInteger& second);
  BigInteger& operator*=(const BigInteger& second);
  BigInteger& operator/=(const BigInteger& second);
  BigInteger& operator%=(const BigInteger& second);

  bool operator==(const BigInteger& second) const;
  bool operator!=(const BigInteger& second) const { return !(*this == second);}

 private:
  std::vector<uint> digits;  // Вначале младшие разряды
  bool is_positive;  // true, если положительно или 0

  bool IsNull() const { return digits.empty(); }

  friend std::istream& operator>>(std::istream& stream, BigInteger& bigint);
};

std::istream& operator>>(std::istream& stream, BigInteger& bigint);

std::ostream& operator<<(std::ostream& stream, const BigInteger& bigint);


// ============================================================================================
// biginteger.cpp

#include "biginteger.h"

#include <limits>

void BigIntegerOld::SetValue(long long value) {
  value_ = value;
}

BigIntegerOld CreateVeryBigInteger() {
  BigIntegerOld bigint;
  bigint.SetValue(std::numeric_limits<long long>::max());
  return bigint;
}

std::string BigInteger::ToString() const {
  if (IsNull()) return "0";
  std::string result;
  if (!is_positive) result.push_back('-');
  for (int i = digits.size() - 1; i >= 0; --i) {
    result.push_back(char(digits[i]) + '0');
  }
  return result;
}

std::istream& operator>>(std::istream& stream, BigInteger& bigint) {
  std::string s;
  stream >> s;
  bigint.is_positive = s[0] != '-';
  for (int i = s.size() - 1; i >= (bigint.is_positive ? 0 : 1); --i) {
    bigint.digits.push_back(s[i] - '0');
  }
  if (bigint.digits.back() == 0) bigint.digits.pop_back();
  return stream;
}

std::ostream& operator<<(std::ostream& stream, const BigInteger& bigint) {
  return stream << bigint.ToString();
}


// ============================================================================================
// main.cpp

#include <algorithm>
#include <iostream>
#include <vector>

#include "biginteger.h"
#include "help.h"

//        0
//   1      3   4
//   2      5
// 6 7 8

// 9
// 0 1   0 3   0 4   1 2   3 5   2 6   2 7   2 8

struct TreeNode {
  int Count = 1;  // Число вершин в поддереве
  int A = 0;  // Сумма длин путей до всех дочерних вершин
  int Result = 0;
  std::vector<int> Children;
};

void DFS1(std::vector<TreeNode>& nodes, int /*Текущая*/ v) {
  for (int k : nodes[v].Children) {
    DFS1(nodes, k);
    nodes[v].Count += nodes[k].Count;
    nodes[v].A += nodes[k].A;
  }
  nodes[v].A += nodes[v].Count - 1;
}

void UpdateChild(std::vector<TreeNode>& nodes, int vert, int child) {
  nodes[child].Result = nodes[vert].Result - nodes[child].Count + nodes.size() - nodes[child].Count;
}

int main1() {
  int n = 0;
  std::cin >> n;
  // Вектор из n узлов.
  std::vector<TreeNode> nodes(n);
  for (int i = 1; i < n; ++i) {
    int a = 0, aa = 0;
    std::cin >> a >> aa;
    if (a > aa) std::swap(a, aa);
    nodes[a].Children.push_back(aa);
  }

  DFS1(nodes, 0);
  UpdateChild(nodes, 0, 1);
  // std::cout << DFS2(nodes) << std::endl;
  return 0;
}

int main2() {
  BigIntegerOld bigint;
  bigint.SetValue(300);
  std::cout << bigint.Value() << std::endl;
  std::cout << CreateVeryBigInteger().Value() << std::endl;
  return 0;
}

int main() {
  BigInteger bigint;
  std::cin >> bigint;
  std::cout << bigint.ToString() << std::endl;
  std::cout << bigint << std::endl;

  return 0;
}