Solution:

这是道启发式合并模板题.

所以要怎么启发式合并呢?

首先求出所有节点的重孩子,然后求这个节点及其子树内的答案时,先处理非重孩子子树的答案,然后清空,然后处理重孩子子树答案,不清空,继承到这里,然后再加上非重孩子子树答案.复杂度是和树链剖分一样的.

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         using namespace std;#define ll long longconst int MAXN=100000;const int MAXM=200000;int n;int col[MAXN+10];int fir[MAXN+10],nxt[MAXM+10],v[MAXM+10],tot;void adde(int from,int to){    ++tot;    v[tot]=to;nxt[tot]=fir[from];    fir[from]=tot;}int sz[MAXN+10],hson[MAXN+10],l[MAXN+10],r[MAXN+10],a[MAXN+10],dfstime;void getsz(int u,int fa){    sz[u]=1;l[u]=++dfstime;a[dfstime]=u;    for(int e=fir[u];e;e=nxt[e])    {        if(v[e]==fa)continue;        getsz(v[e],u);        sz[u]+=sz[v[e]];        if(sz[hson[u]]