U41492 樹上數顔色(dsu)

U41492 樹上數顔色

題意：

輸入 n ( 1 e 5 ) n(1e5) n(1e5)表示一棵根為1的樹有 n n n個節點

接下來 n − 1 n-1 n−1行每行 u , v u,v u,v表示樹邊

接下來一行 n n n個數， c 1 , c 2 , … , c n ( 1 ≤ c i ≤ n ) c_1,c_2,\dots,c_n(1\leq c_i\leq n) c1​,c2​,…,cn​(1≤ci​≤n)表示節點顔色

接下來 m ( m ≤ n ) m(m\leq n) m(m≤n)個詢問,每個詢問詢問一顆子樹有多少個顔色。

題意：

用樹上啟發式合并(dsu)

先重鍊剖分出重兒子。

操作

• 先處理輕兒子，并把結果消去
• 處理重兒子，把結果保留
• 最後把輕兒子的貢獻加上

做法很暴力，但是複雜度就是 n log ⁡ ( n ) n\log(n) nlog(n)。

代碼：

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+9;
int c[N],ans[N];
struct Edge{
    int v,nxt;
}e[N<<1];
int head[N],cnt;
int n;
inline void add(int u,int v){
    e[cnt]=(Edge){v,head[u]};
    head[u]=cnt++;
}
int son[N],siz[N];
void dfs(int u,int fa){
    siz[u]=1;
    for(int i=head[u];~i;i=e[i].nxt){
        Edge e1=e[i];
        if(e1.v==fa)continue;
        dfs(e1.v,u);
        siz[u]+=siz[e1.v];
        if(siz[son[u]]<siz[e1.v])son[u]=e1.v;
    }
}
int he[N],nowson,sum;
void calc(int u,int fa,int val){
//    cout<<"calc "<<u<<" "<<fa<<" "<<val<<endl;
    if(!he[c[u]])sum++;
    he[c[u]]+=val;
    for(int i=head[u];~i;i=e[i].nxt){
        Edge e1=e[i];
        if(e1.v==fa||e1.v==nowson)continue;
        calc(e1.v,u,val);
    }
}
void dsu(int u,int fa,bool kep){
 //   cout<<"dsu "<<u<<" "<<fa<<" "<<kep<<endl;
    for(int i=head[u];~i;i=e[i].nxt){
        Edge e1=e[i];
        if(e1.v==fa||e1.v==son[u])continue;
        dsu(e1.v,u,0);
    }
    if(son[u])dsu(son[u],u,1),nowson=son[u];
    calc(u,fa,1);nowson=0;
    ans[u]=sum;
    if(!kep){
        calc(u,fa,-1);
        sum=0;
    }
}
int main(){
  //  freopen("tt.in","r",stdin),freopen("tt.out","w",stdout);
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n;
    memset(head,-1,sizeof(head));
    for(int i=1,u,v;i<n;i++){
        cin>>u>>v;
        add(u,v),add(v,u);
    }
    for(int i=1;i<=n;i++)cin>>c[i];
    dfs(1,0);
    dsu(1,0,1);
    int m;
    cin>>m;
    while(m--){
        int t;
        cin>>t;
        cout<<ans[t]<<endl;
    }
    return 0;
}