1187E - Tree Painting - CodeForces Solution

/*
    
███████╗  ░░░░░░  ██╗░░██╗  ███████╗  ███╗░░██╗  ███████╗
╚════██║  ░░░░░░  ██║░██╔╝  ██╔════╝  ████╗░██║  ╚════██║
░░███╔═╝  █████╗  █████═╝░  █████╗░░  ██╔██╗██║  ░░░░██╔╝
██╔══╝░░  ╚════╝  ██╔═██╗░  ██╔══╝░░  ██║╚████║  ░░░██╔╝░
███████╗  ░░░░░░  ██║░╚██╗  ███████╗  ██║░╚███║  ░░██╔╝░░
╚══════╝  ░░░░░░  ╚═╝░░╚═╝  ╚══════╝  ╚═╝░░╚══╝  ░░╚═╝░░░
    
*/
#include <bits/stdc++.h>
using namespace std;
#define all(a) (a).begin(), (a).end()
#define INFI INT32_MAX
#define INFL INT64_MAX
#define endl '\n'
#define yn(flag) cout << ((flag) ? "YES" : "NO") << endl
typedef long long ll; typedef vector<int> vi; typedef vector<vi> vvi; typedef vector<vvi> vvvi; typedef vector<long long> vl; 
typedef vector<vl> vvl; typedef vector<vvl> vvvl; typedef vector<string> vs; typedef vector<vs> vvs;
typedef vector<bool> vb; typedef vector<vb> vvb; typedef pair<int, int> pii; typedef pair<ll, ll> pll;
typedef pair<ll, int> pli; typedef pair<int, ll> pil; typedef vector<pii> vpii; 
const int diri[8] = { -1, 0, 0, 1, -1, -1, 1, 1 }; const int dirj[8] = { 0, 1, -1, 0, -1, 1, -1, 1 };
template<typename T,typename V> ostream& operator<<(ostream &s,pair<T,V> t) {return s<<"{"<<t.first<<","<<t.second<<"}";}
template<typename T> ostream& operator<<(ostream &s,vector<T> t) {s << "[";for (int i = 0; i < t.size(); ++i) {s << t[i];
if (i != t.size() - 1) {s << ", ";}}s << "]";return s;}
template<typename T, typename V> ostream& operator<<(ostream &s,map<T, V> t) {s << "{";for (auto& a : t) {s << a << " ";} s << "}";return s;}
template<typename T> ostream& operator<<(ostream &s, set<T> t) {s << "{";for (auto& a : t) {s << a << ", ";} s << "}";return s;}
template<typename... T> void put(T&&... args) { ((cout << args << " "), ...);}
template<typename... T> void putl(T&&... args) { ((cout << args << " "), ...); cout<<'\n';}
template<typename T> void input(vector<T>& t) { for (auto& v : t) cin >> v; }
const int mod = 1e9+7;

int main() {
   ios_base::sync_with_stdio(false);
   cin.tie(NULL); cout.tie(NULL);
   int n; cin >> n;
   vector<vector<int>> graph(n + 1);
   for (int i = 0; i < n - 1; ++i) {
      int a, b;
      cin >> a >> b;
      graph[a].push_back(b);
      graph[b].push_back(a);
   }
   vector<int> dp(n + 1); // Number of nodes 
   function<int(int, int)> init_dfs = [&](int v, int p) {
      int count = 1;
      for (auto to : graph[v]) 
         if (to != p) 
            count += init_dfs(to, v);
      return dp[v] = count;
   };
   init_dfs(1, -1);
   long long sum = accumulate(dp.begin(), dp.end(), 0LL);
   long long res = sum;
   function<void(int, int, long long)> dfs = [&](int v, int p, long long current_res) {
      res = max(res, current_res);
      for (auto to : graph[v]) 
         if (to != p) 
            dfs(to, v, current_res + n - 2 * dp[to]);
   };
   dfs(1, -1, res);
   cout << res << endl;
   return 0;
}

/* Try this if you are stuck:
1) Maybe binary search on answer?
2) Try solving it in reverse
3) Think of a simple problem 
4) Think of elements which are special
   (like minimum, maximum, deepest node in tree, root)
5) Is it graph problem?
*/
/* DONT FORGET:
   EDGE CASES!!!!!
   N = 1,2...
   LONG LONG INSTEAD OF INT??
*/