CF741D Arpa’s letter-marked tree and Mehrdad’s Dokhtar-kosh paths

CF741D Arpa’s letter-marked tree and Mehrdad’s Dokhtar-kosh paths

好像这个题只能Dsu On Tree？

有根树点分治

统计子树过x的路径

奇偶可以xor，深度可以减，所以，w[x]x到根的链上二进制数S保留字符出现奇偶性

mx[S]表示w[x]=S的x的最大深度

类比点分治去做

更新答案时候处理一个轻儿子回来更新mx[]

重儿子贡献的答案额外处理。

#include<bits/stdc++.h>

#define reg register int

#define il inline

#define fi first

#define se second

#define mk(a,b) make_pair(a,b)

#define numb (ch^'0')

using namespace std;

typedef long long ll;

template<class T>il void rd(T &x){

    char ch;x=;bool fl=false;

    while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true);

    for(x=numb;isdigit(ch=getchar());x=x*+numb);

    (fl==true)&&(x=-x);

}

template<class T>il void ot(T x){x/?ot(x/):putchar(x%+'');}

template<class T>il void prt(T a[],int st,int nd){for(reg i=st;i<=nd;++i) printf("%lld ",a[i]);putchar('\n');}

namespace Miracle{

const int N=5e5+;

const int inf=0x3f3f3f3f;

int n,m;

struct node{

    int nxt,to;

    int val;

}e[*N];

int hd[N],cnt;

void add(int x,int y,int z){

    e[++cnt].nxt=hd[x];

    e[cnt].to=y;

    e[cnt].val=z;

    hd[x]=cnt;

}

int sz[N],son[N];

int w[N];

int dep[N];

void dfs(int x,int d){

    sz[x]=;

    dep[x]=d;

    for(reg i=hd[x];i;i=e[i].nxt){

        int y=e[i].to;

        w[y]=w[x]^(<<e[i].val);

        dfs(y,d+);

        sz[x]+=sz[y];

        if(sz[y]>sz[son[x]]) son[x]=y;

    }

}

int mx[<<];

int ans[N];

int Son;

pair<int,int>mem[N];

int tot;

void upda(int x,int id,int val){

    if(val==-) mx[w[x]]=-inf;

    if(val==){

        ans[id]=max(ans[id],mx[w[x]]+dep[x]-*dep[id]);

        for(reg i=;i<;++i){

            ans[id]=max(ans[id],mx[w[x]^(<<i)]+dep[x]-*dep[id]);

        }

        mem[++tot]=mk(w[x],dep[x]);

    }

    for(reg i=hd[x];i;i=e[i].nxt){

        int y=e[i].to;

        upda(y,id,val);

    }

}

void sol(int x,int op){

    for(reg i=hd[x];i;i=e[i].nxt){

        int y=e[i].to;

        if(y==son[x]) continue;

        sol(y,);

    }

    if(son[x]) sol(son[x],);

    mx[w[x]]=max(mx[w[x]],dep[x]);

    if(son[x]){

        ans[x]=max(ans[x],mx[w[x]]-dep[x]);

        for(reg i=;i<;++i){

            ans[x]=max(ans[x],mx[w[x]^(<<i)]-dep[x]);

        }

    }

    for(reg i=hd[x];i;i=e[i].nxt){

        int y=e[i].to;

        ans[x]=max(ans[x],ans[y]);

        if(y!=son[x]){

            tot=;

            upda(y,x,);

            for(reg j=;j<=tot;++j){

                mx[mem[j].fi]=max(mx[mem[j].fi],mem[j].se);

            }

        }

    }

    if(op==){

        upda(x,x,-);

    }

}

int main(){

    rd(n);

    char ch[];

    int fa;

    memset(mx,-inf,sizeof mx);

    for(reg i=;i<=n;++i){

        rd(fa);

        scanf("%s",ch+);

        add(fa,i,ch[]-'a');

    }

    dfs(,);

    sol(,);

    for(reg i=;i<=n;++i){

        printf("%d ",ans[i]);

    }

    return ;

}

}

signed main(){

    Miracle::main();

    return ;

}

/*

   Author: *Miracle*

   Date: 2019/3/10 10:32:24

*/

Dsu 由于“精确打击”，可以类比点分治处理有根树的路径了。只要维护好重儿子的信息

但是缺点同样明显：如果信息不具有可减性，就没法做了