首页 > 代码库 > cfodeforces 741D Arpa’s letter-marked tree and Mehrdad’s Dokhtar-kosh paths
cfodeforces 741D Arpa’s letter-marked tree and Mehrdad’s Dokhtar-kosh paths
题目链接:Arpa’s letter-marked tree and Mehrdad’s Dokhtar-kosh paths
第一次写\(dsu\ on\ tree\),来记录一下
\(dsu\ on\ tree\)主要维护子树信息,往往可以省掉一个数据结构的启发式合并。大体思路如下:
轻重链路径剖分之后,对每个点先递归处理他的所有轻儿子,每次处理完轻儿子之后把这棵子树的信息清空。最后再来处理重孩子,重儿子的信息就可以不用清空了。由于我们是用一个全局数组来记录信息的,重儿子子树的信息就仍然保留在全局数组中。接着我们另外写一个函数\(dfs\)所有的轻儿子子树,并统计答案。每统计完一棵子树的答案就可以把这棵子树的信息计入全局数组中,用于下一次更新。由于每个点到根的轻边条数是\(\log n\)级别的,所以每个点最多被扫\(\log n\)遍。
回到这道题上来。由于要求路径上的所有字符重新排列之后可以形成一个回文串,也就是说出现次数为奇数的字符不会超过\(1\)个。那么我们就可以给每个字符一个\(2^x\)形式的权值,这样的话合法路径的异或和要么为\(0\),要么为\(2^x\)的形式。
设点\(x\)到根的异或和为\(D_x\),由于这道题是边权,\(x\)和\(y\)路径上的异或和就可以用\(D_x\ xor\ D_y\)来表示。这样的话就可以用一个数组\(c\)来统计答案,其中\(c_i\)表示满足\(D_x=i\)的\(x\)的最大深度。剩下的就是套\(dsu\ on\ tree\)的板子了。
下面贴代码:
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<cmath> #define File(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout) #define maxn 500010 #define INF (1<<30) using namespace std; typedef long long llg; int n,ci[1<<22],son[maxn],siz[maxn],dep[maxn]; int hd[maxn],nt[maxn],D[maxn],ans[maxn]; int getint(){ int w=0;bool q=0; char c=getchar(); while((c>‘9‘||c<‘0‘)&&c!=‘-‘) c=getchar(); if(c==‘-‘) c=getchar(),q=1; while(c>=‘0‘&&c<=‘9‘) w=w*10+c-‘0‘,c=getchar(); return q?-w:w; } void dfs(int u){ siz[u]=1; for(int i=hd[u];i;i=nt[i]){ D[i]^=D[u]; dep[i]=dep[u]+1; dfs(i); siz[u]+=siz[i]; if(siz[i]>siz[son[u]]) son[u]=i; } } void undo(int u){ ci[D[u]]=-INF; for(int i=hd[u];i;i=nt[i]) undo(i); } int o; void up(int &x,int y){if(y>x) x=y;} void up(int u){ up(ans[o],dep[u]+ci[D[u]]); for(int i=0;i<=21;i++) up(ans[o],dep[u]+ci[1<<i^D[u]]); for(int i=hd[u];i;i=nt[i]) up(i); } void ins(int u){ up(ci[D[u]],dep[u]); for(int i=hd[u];i;i=nt[i]) ins(i); } void work(int u){ for(int i=hd[u];i;i=nt[i]) if(i!=son[u]) work(i),undo(i); if(son[u]) work(son[u]); o=u; for(int i=hd[u];i;i=nt[i]) if(i!=son[u]) up(i),ins(i); up(ci[D[u]],dep[u]); up(ans[u],dep[u]+ci[D[u]]); for(int i=0;i<=21;i++) up(ans[u],dep[u]+ci[1<<i^D[u]]); ans[u]-=dep[u]<<1; for(int i=hd[u];i;i=nt[i]) up(ans[u],ans[i]); } int main(){ File("a"); n=getint(); for(int i=0;i<(1<<22);i++) ci[i]=-INF; for(int i=2,x;i<=n;i++){ x=getint(); nt[i]=hd[x];hd[x]=i; char c=getchar(); while(c>‘v‘ || c<‘a‘) c=getchar(); D[i]=1<<(c-‘a‘); } dfs(1); work(1); for(int i=1;i<=n;i++) printf("%d ",ans[i]); return 0; }
cfodeforces 741D Arpa’s letter-marked tree and Mehrdad’s Dokhtar-kosh paths