CF741D Arpa’s letter-marked tree and Mehrdad’s Dokhtar-ko

dsu on tree。

第一次写，还有点蒙。

dsu on tree 核心思想就是利用轻重儿子减去一个儿子（重儿子）的计算，从而将 $o(n^2)$ 的算法打到 $o(nlogn)$ 。

这个题目，是回文串的话我们可以只关注一个回文串中每一个字母的出现次数。比如说 $abcba$ ，出现次数分别是 $2,2,1$ ，两奇一偶；$abccba$ ，出现次数为 $2,2,2$ ，都是偶数。。。因此一个回文串中至多出现一个出现奇数次的字母。。。

奇。。。偶。。。很显然是 $0$ 和 $1$ ，而且 $22$ 个字母，明摆着要状压。。。于是每个点开一个数组，$d_i$ 表示 $1$ 节点到 $i$ 节点上的路径状压后的结果。。。

对于一个点 $u$ ，假设它有一堆儿子 $v$ ，要更新这个 $u$ 的子树的结果，就从 $u$ 递归下去遍历整颗子树；对于每个点，为回文串的状压路径值可能是 $1<<k$，不妨 $0$ 至 $21$ 枚举 $k$ ，每一次都尝试着能不能更新 $u$ 的答案就好啦。

为了实现 dsu on tree ，每一次只计算 $u$ 的轻儿子， $u$ 的重儿子先留着，以后单独拿出来算w

具体讲解一下代码吧：

inline void dfs1(ll x){
    val[x]=1;
    for(register int i=hd[x];i;i=e[i].nx){
        ll to=e[i].to;
        d[to]=d[x]^e[i].dis;
        dep[to]=dep[x]+1;
        dfs1(to);
        val[x]+=val[to];
        if(val[son[x]]<val[to]||!son[x])
            son[x]=to;
    }
}

处理 $d$ 数组，$dep$ 数组和轻重链。

for(register int i=hd[x];i;i=e[i].nx)
	if(e[i].to!=son[x]){
		dfs2(e[i].to);
        clean(e[i].to);
}

只遍历 $u$ 的轻儿子，$clean$ 函数用于清零数组，即路径为 $d[x]$ 的节点 $x$ 不再存在啦。。。其实也不是完全清空，递归重儿子的时候还是有可能有 $d[x]$ 的路径，之前的清零只是为了给递归重儿子创造一个新的机会开启一个新的递归w

清零在下面

inline void clean(ll x){
    c[d[x]]=-INF;
    for(register int i=hd[x];i;i=e[i].nx)
        clean(e[i].to);
}

然后就开始疯狂更新答案了。。。分别考虑经过 $u$ 的路径和不经过 $u$ 的路径

inline void init(ll x){
    c[d[x]]=max(c[d[x]],dep[x]);
    for(register int i=hd[x];i;i=e[i].nx)
        init(e[i].to);
}
inline void work(ll nw,ll fm){
    ans[fm]=max(ans[fm],dep[nw]+c[d[nw]]);
    for(register int i=0;i<=21;++i) 
        ans[fm]=max(ans[fm],dep[nw]+c[(1<<i)^(d[nw])]);
    for(register int i=hd[nw];i;i=e[i].nx)
        if(e[i].to!=fm)
            work(e[i].to,fm);
}

for(register int i=hd[x];i;i=e[i].nx){
        ll to=e[i].to;
        if(to==son[x])   continue;
        work(to,x);
        init(to);
    }

上面是更新不经过 $u$ 的答案

下面是更新经过 $u$ 的答案

c[d[x]]=max(c[d[x]],dep[x]);
ans[x]=max(ans[x],dep[x]+c[d[x]]);
for(register int i=0;i<=21;++i)
	ans[x]=max(ans[x],dep[x]+c[1<<i^d[x]]);
ans[x]-=(dep[x]<<1);
for(register int i=hd[x];i;i=e[i].nx)
	ans[x]=max(ans[x],ans[e[i].to]);

完结撒花～