JOI 2013 - Synchronization

Method 1 - ?

When deleting an edge, remember how many systems that edge was used to synchronize. Also, each moment there is a connected component, all computers in the component have the same value.

Andi Qu

^ This is $\mathcal{O}(N{\log }^{2}N)$ I think

If we use HLD or LCT then it's $\mathcal{O}(N\log N)$.

Method 2 - Centroid Decomposition

Looks like $\mathcal{O}(N{\log }^{3}N)$ is very fast!

1#include <bits/stdc++.h>
2using namespace std;
3 
4using ll = long long;
5using ld = long double;
6using db = double; 
7using str = string; // yay python!
8
9using pi = pair<int,int>;
10using pl = pair<ll,ll>;