codeforces 914E 树上点分治-蒲公英云

codeforces 914E 树上点分治

r囧r小猫 2021-12-17 12:19 359阅读 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<<' ';
}