DSU on tree

清疚 2022-12-20 08:39 105阅读 0赞

这次的ccpc 是我演了 我看出了这个不会写 是我的问题

重新开始认真学一遍dsu on tree，之前只是了解了思想就以为自己能摸，结果.....千错万错都是我的错，我演了 dbq

[板子题链接][Link 1]

对于每个节点重儿子子树只统计一遍，轻儿子暴力统计+撤销影响（这一操作是为了重复利用数组，不炸空间），每个轻儿子最多被暴力log次

#include<bits/stdc++.h>
    using namespace std;
    const int N=2e5+7;
    typedef long long ll;
    const ll inf=1e18;
    const int mod=998244353;
    vector<int>son[N];
    int siz[N];
    int er[N];
    int a[N];
    int cnt[N];
    ll Son,sum=0;
    ll ans[N];
    int ma;
    void dfs(int x,int fa)
    {
        siz[x]=1;
        for(int i=0;i<son[x].size();i++)
        {
            int d=son[x][i];
            if(d==fa) continue;
            dfs(d,x);
            if(siz[d]>siz[er[x]]) er[x]=d;
            siz[x]+=siz[d];
        }
    }
    void add(int x,int fa,int val)
    {
    
        cnt[a[x]]+=val;
        if(cnt[a[x]]>ma) ma=cnt[a[x]],sum=a[x];
        else if(cnt[a[x]]==ma) sum+=a[x];
        for(int i=0;i<son[x].size();i++)
        {
            int d=son[x][i];
            if(d==fa||d==Son) continue;
            add(d,x,val);
        }
    }
    void dfs2(int x,int fa,int op)
    {
        //cout<<x<<' '<<'?'<<endl;
        for(int i=0;i<son[x].size();i++)
        {
            int d=son[x][i];
            if(d==fa||d==er[x]) continue;
            dfs2(d,x,0);
        }
        if(er[x])dfs2(er[x],x,1),Son=er[x];
        add(x,fa,1);Son=0;
        ans[x]=sum;
        //cout<<'!'<<x<<' '<<ans[x]<<' '<<ma<<endl;
        if(!op) add(x,fa,-1),sum=0,ma=0;//撤销轻儿子影响
    }
    signed main()
    {
        int n;
        cin>>n;
        for(int i=1;i<=n;i++)
            cin>>a[i];
        for(int i=1;i<n;i++)
        {
            int a1,a2;
            cin>>a1>>a2;
            son[a1].push_back(a2);
            son[a2].push_back(a1);
        }
        //son[1].push_back(0);
        dfs(1,0);
        //for(int i=1;i<=n;i++) cout<<er[i]<<' ';cout<<endl;
        dfs2(1,0,0);
    
        for(int i=1;i<=n;i++)
            cout<<ans[i]<<' ';
        cout<<endl;
    }

长春的题明天补了再放代码

已补

题目大意给你一棵树，每个节点都有个权值，如果a\[i\]^a\[j\]=a\[lca(i,j)\] ans+=(i^j)

板子题，和上面那题差不多就是要注意枚举最近公共祖先节点时，需要先把轻儿子子树的贡献算了，再把轻儿子子树加进数组中

AC代码

#include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    #define int ll
    const int N=2e5+7;
    const ll inf=1e18;
    const int mod=998244353;
    vector<int>son[N];
    int siz[N];
    int er[N];
    int a[N];
    int cnt[N*6][20];
    int num[N*6];
    ll Son,sum=0;
    ll ans;
    int ma;int n;
    void dfs(int x,int fa)
    {
        siz[x]=1;
        for(int i=0;i<son[x].size();i++)
        {
            int d=son[x][i];
            if(d==fa) continue;
            dfs(d,x);
            if(siz[d]>siz[er[x]]) er[x]=d;
            siz[x]+=siz[d];
        }
    }
    void gai(int x,int fa,int val)
    {
    
        for(int i=0;i<20;i++)
        {
            if(x&(1<<i))
            cnt[a[x]][i]+=val;
        }
        num[a[x]]+=val;
        for(int i=0;i<son[x].size();i++)
        {
            int d=son[x][i];
            if(d==fa) continue;
            gai(d,x,val);
        }
    
    }
    
    void add(int x,int fa,int zu)
    {
        int d=a[x]^a[zu];
            //cout<<x<<' '<<d<<' '<<zu<<'!'<<' '<<num[d]<<endl;
        for(int i=0;i<20;i++)
        {
            if(x&(1<<i))
                ans+=(num[d]-cnt[d][i])*(1<<i);
    
            else
                ans+=cnt[d][i]*(1<<i);
        }
        for(int i=0;i<son[x].size();i++)
        {
            int d=son[x][i];
            if(d==fa||d==Son) continue;
            add(d,x,zu);
        }
    
    }
    
    void dfs2(int x,int fa,int op)
    {
        //cout<<x<<' '<<'?'<<endl;
        for(int i=0;i<son[x].size();i++)
        {
            int d=son[x][i];
            if(d==fa||d==er[x]) continue;
            dfs2(d,x,0);
        }
        if(er[x]) dfs2(er[x],x,1),Son=er[x];
       /* for(int i=1;i<=n;i++)
        {
            for(int j=0;j<4;j++)
                 cout<<cnt[i][j]<<' ';
            cout<<endl;
        }*/
    
         for(int i=0;i<son[x].size();i++)
        {
            int d=son[x][i];
            if(d==fa||d==er[x]) continue;
            add(d,x,x);
            gai(d,x,1);
        }
        for(int i=0;i<20;i++)
        {
            if(x&(1<<i))
            cnt[a[x]][i]++;
        }
        num[a[x]]++;
        //cout<<'?'<<x<<' '<<ans<<endl;
       /*for(int i=1;i<=n;i++)
        {
            for(int j=0;j<4;j++)
                 cout<<cnt[i][j]<<' ';
            cout<<endl;
        }*/
        //cout<<"SSSSSSSS"<<endl;
        Son=0;
        if(!op)
        {
        for(int i=0;i<20;i++)
        {
            if(x&(1<<i))
            cnt[a[x]][i]--;
        }
        num[a[x]]--;
        for(int i=0;i<son[x].size();i++)
        {
            int d=son[x][i];
            if(d==fa) continue;
            gai(d,x,-1);
        }
        }
    }
    signed main()
    {
    
        cin>>n;
        for(int i=1;i<=n;i++)
            cin>>a[i];
        for(int i=1;i<n;i++)
        {
            int a1,a2;
            cin>>a1>>a2;
            son[a1].push_back(a2);
            son[a2].push_back(a1);
        }
        //son[1].push_back(0);
        dfs(1,0);
        //for(int i=1;i<=n;i++) cout<<er[i]<<' ';cout<<endl;
        dfs2(1,0,0);
        cout<<ans<<endl;
    }
    /*
    7
    2 1 7 6 3 2 3
    1 2
    1 2
    1 4
    1 5
    2 6
    3 7
    */

[Link 1]: https://codeforces.com/contest/600/problem/E