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 $O(N\log^2N)$ I think

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

Method 2 - Centroid Decomposition

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

vpi adj[MX];
int N,M,Q,ans[MX];
vi change[MX];
vpi bad[MX];
 
bool done[MX]; // processed as centroid yet
int sub[MX],cen[MX]; // subtree size, centroid anc
map<int,list<int>> to[MX], from[MX];
void dfs(int x, int p) { sub[x] = 1; 
    trav(y,adj[x]) if (!done[y.f] && y.f != p)