codeforces 914E 树上点分治

r囧r小猫 2021-12-17 12:19 225阅读 0赞

https://codeforc.es/contest/914/problem/E

题解:

首先,这个是一个可减的信息,需要容斥去做

对于信息而言,显然是状压保存,然后用数组去记录出现次数

对于一个点,当前点的ans是这样统计的:

1.计算整棵树的贡献,

2.对于根的每个儿子,先删除他的贡献,然后计算一次该子树的贡献,然后再加回来

3.删除整棵树的贡献

由于dis(a,b)和dis(b,a)会重复统计,因此对于根的贡献要/2

而其他节点,由于是走一步算一步,因此只会算一遍

#include<bits/stdc++.h>
    #define endl '\n'
    #define ll long long
    #define pii pair<ll,int>
    #define all(x) x.begin(),x.end()
    #define IO ios::sync_with_stdio(false)
    #define rep(ii,a,b) for(int ii=a;ii<=b;++ii)
    #define per(ii,a,b) for(int ii=b;ii>=a;--ii)
    #define forn(i,x) for(int i=head[x];i;i=e[i].next)
    using namespace std;
    const int maxn=4e5+10,maxm=4e5+10;
    const int INF=0x3f3f3f3f;
    const int mod=1e9+7;
    const double PI=acos(-1.0);
    int casn,n,m;
    ll k;
    string s;
    int num[maxn];
    class graph{public:
      struct node{int to,next;ll cost;}e[maxm];
      int head[maxn],nume,n,sz[maxn],maxt,stree[maxn];
      void add(int a,int b,ll c=0){e[++nume]={b,head[a],c};head[a]=nume;}
      int vis[maxn],all,mid;
      void getmid(int now=1,int pre=0){
        sz[now]=1;
        for(int i=head[now];i;i=e[i].next){
          if(e[i].to==pre||vis[e[i].to]) continue;
          getmid(e[i].to,now);
          sz[now]+=sz[e[i].to];
        }
        int tmp=max(sz[now]-1,all-sz[now]);
        if(maxt>tmp) maxt=tmp,mid=now;
      }//base
      int cnt[1<<20|10];
      ll ans[maxn];
      void init(int n){
        this->n=n,nume=1,mid=0;
        rep(i,1,n) vis[i]=head[i]=0;
      }
      void update(int now,int pre,int flag,int d){
        d^=num[now];cnt[d]+=flag;
        for(int i=head[now];i;i=e[i].next){
            int to=e[i].to;
            if(to==pre||vis[to]) continue;
            update(to,now,flag,d);
        }
      }
      ll getdis(int now,int pre,int d){
        d^=num[now];ll sum=cnt[d];
        rep(i,0,19) sum+=cnt[d^(1<<i)];
        for(int i=head[now];i;i=e[i].next){
          int to=e[i].to;
          if(to==pre||vis[to]) continue;
          sum+=getdis(to,now,d);
        }
        ans[now]+=sum;
        return sum;
      }
      void getans(int now){
        update(now,0,1,0);
        ll sum=cnt[0];
        rep(i,0,19) sum+=cnt[1<<i];
        for(int i=head[now];i;i=e[i].next){
            int to=e[i].to;
            if(vis[to]) continue;
            update(to,now,-1,num[now]);
            sum+=getdis(to,now,0);
            update(to,now,1,num[now]);
        }
        update(now,0,-1,0);
        ans[now]+=sum/2;
      }
      void divide(int now){
        vis[now]=1;getans(now);
        for(int i=head[now];i;i=e[i].next){
          int to=e[i].to;
          if(vis[to]) continue;
          all=sz[to],maxt=n+1;
          getmid(to,now);divide(mid);
        }
      }
      void solve(){
        maxt=all=n;memset(ans,0,(sizeof ans[0])*(n+1));
        getmid();divide(mid);
      }
    }g;
    
    int main() {IO;
      cin>>n;
      g.init(n);
      rep(i,2,n){
        int a,b;cin>>a>>b;
        g.add(a,b);g.add(b,a);
      }
      cin>>s;s=" "+s;
      rep(i,1,n){
        num[i]=(1<<(s[i]-'a'));
      }
      g.solve();
      rep(i,1,n) cout<<g.ans[i]+1<<' ';
    }

转载于:https://www.cnblogs.com/nervendnig/p/10911674.html