关于dsu on tree 和一些例题 CF 741 D

题意：http://codeforces.com/problemset/problem/741/D

求各个子树的最长回文链，字符可任意组合

思路：

其实肯定是要转换成进制状压的

也是dsu on tree的模板题

这里由于保留重子树要上升一条链（因为值是在边上的）

更新不太好更新，我一开始一直想着从当前根往下记录，这样非常难搞

但是从上往下就很好搞，直接记录pos点向上的整条链，两条链异或也就是那条折链（思路就出来了

代码细节还是有点的，本人debug 滴不出来就不搞了==|||

update 2020 4 23:

de出来了

  1 #define IOS ios_base::sync_with_stdio(0); cin.tie(0);
  2 #include <cstdio>//sprintf islower isupper
  3 #include <cstdlib>//malloc  exit strcat itoa system("cls")
  4 #include <iostream>//pair
  5 #include <fstream>//freopen("C:\Users\13606\Desktop\Input.txt","r",stdin);
  6 #include <bitset>
  7 //#include <map>
  8 //#include<unordered_map>
  9 #include <vector>
 10 #include <stack>
 11 #include <set>
 12 #include <string.h>//strstr substr strcat
 13 #include <string>
 14 #include <time.h>// srand(((unsigned)time(NULL))); Seed n=rand()%10 - 0~9;
 15 #include <cmath>
 16 #include <deque>
 17 #include <queue>//priority_queue<int, vector<int>, greater<int> > q;//less
 18 #include <vector>//emplace_back
 19 //#include <math.h>
 20 #include <cassert>
 21 #include <iomanip>
 22 //#include <windows.h>//reverse(a,a+len);// ~ ! ~ ! floor
 23 #include <algorithm>//sort + unique : sz=unique(b+1,b+n+1)-(b+1);+nth_element(first, nth, last, compare)
 24 using namespace std;//next_permutation(a+1,a+1+n);//prev_permutation
 25 //******************
 26 clock_t __START,__END;
 27 double __TOTALTIME;
 28 void _MS(){__START=clock();}
 29 void _ME(){__END=clock();__TOTALTIME=(double)(__END-__START)/CLOCKS_PER_SEC;cout<<"Time: "<<__TOTALTIME<<" s"<<endl;}
 30 //***********************
 31 #define rint register int
 32 #define fo(a,b,c) for(rint a=b;a<=c;++a)
 33 #define fr(a,b,c) for(rint a=b;a>=c;--a)
 34 #define mem(a,b) memset(a,b,sizeof(a))
 35 #define pr printf
 36 #define sc scanf
 37 #define ls rt<<1
 38 #define rs rt<<1|1
 39 typedef pair<int,int> PII;
 40 typedef vector<int> VI;
 41 typedef unsigned long long ull;
 42 typedef long long ll;
 43 typedef double db;
 44 const db E=2.718281828;
 45 const db PI=acos(-1.0);
 46 const ll INF=(1LL<<60);
 47 const int inf=(1<<30);
 48 const db ESP=1e-9;
 49 const int mod=(int)1e9+7;
 50 const int N=(int)1e6+10;
 51 
 52 struct EDGE
 53 {
 54     int to,next;
 55     int c;
 56 }edge[N<<1];
 57 int tot;
 58 int head[N];
 59 void add(int from,int to,int c)
 60 {
 61     ++tot;
 62     edge[tot].to=to;
 63     edge[tot].c=c;
 64     edge[tot].next=head[from];
 65     head[from]=tot;
 66 }//for(int i=head[x];i;i=edge[i].next)
 67 
 68 int sz[N],Bigson[N],vb[N],dis[N],deep[N];
 69 char s[N];
 70 int ans[N];
 71 void dfs(int x,int fa,int dep,int val)
 72 {
 73     sz[x]=1;
 74     dis[x]=val;
 75     deep[x]=dep;
 76     for(int i=head[x];i;i=edge[i].next)
 77     {
 78         int to=edge[i].to;
 79         if(to==fa)continue;
 80         dfs(to,x,dep+1,val^edge[i].c);
 81         sz[x]+=sz[to];
 82         if(sz[Bigson[x]]<sz[to])
 83             Bigson[x]=to,vb[x]=edge[i].c;
 84     }
 85 }
 86 
 87 int Son;
 88 bool okself(int xx)
 89 {
 90     bool ok=0;
 91     if(xx==0)ok=1;
 92     for(int i=1;i<=22;++i)
 93         if((xx^(1<<(i-1)))==0)ok=1;
 94     return ok;
 95 }
 96 int mark[1<<23];
 97 
 98 void goself(int x,int fa,int who)
 99 {
100     mark[dis[x]]=max(mark[dis[x]],deep[x]);
101     if(okself(dis[x]^dis[who]))ans[who]=max(ans[who],deep[x]-deep[who]);
102     for(int i=head[x];i;i=edge[i].next)
103     {
104         int to=edge[i].to;
105         if(to==fa||to==Son)continue;
106         goself(to,x,who);
107     }
108 }
109 void go(int x,int fa,int who)
110 {
111     if(mark[dis[x]])ans[who]=max(ans[who],mark[dis[x]]+deep[x]-2*deep[who]);
112     for(int i=1;i<=22;++i)
113         if(mark[dis[x]^(1<<(i-1))])ans[who]=max(ans[who],mark[dis[x]^(1<<(i-1))]+deep[x]-2*deep[who]);
114     for(int i=head[x];i;i=edge[i].next)
115     {
116         int to=edge[i].to;
117         if(to==fa||to==Son)continue;
118         go(to,x,who);
119     }
120 }
121 void del(int x,int fa)
122 {
123     mark[dis[x]]=0;
124     for(int i=head[x];i;i=edge[i].next)
125     {
126         int to=edge[i].to;
127         if(to==fa)continue;
128         del(to,x);
129     }
130 }
131 
132 void dfs2(int x,int fa,int op)//保证回溯时,重儿子数据全留,轻儿子数据全没有
133 {
134     for(int i=head[x];i;i=edge[i].next)
135     {
136         int to=edge[i].to;
137         if(to==fa)continue;
138         if(to!=Bigson[x])dfs2(to,x,0),ans[x]=max(ans[x],ans[to]);
139     }
140     if(Bigson[x])dfs2(Bigson[x],x,1),ans[x]=max(ans[x],ans[Bigson[x]]);
141 
142     Son=Bigson[x];
143     if(mark[dis[x]])ans[x]=max(ans[x],mark[dis[x]]-deep[x]);
144     for(int i=1;i<=22;++i)
145         if(mark[dis[x]^(1<<(i-1))])ans[x]=max(ans[x],mark[dis[x]^(1<<(i-1))]-deep[x]);
146     mark[dis[x]]=max(mark[dis[x]],deep[x]);
147     for(int i=head[x];i;i=edge[i].next)
148     {
149         int to=edge[i].to;
150         if(to==fa)continue;
151         if(to!=Bigson[x])
152             go(to,x,x),goself(to,x,x);
153     }
154 
155     if(!op)del(x,fa);
156 }
157 
158 int main()
159 {
160     int n;
161     sc("%d",&n);
162     for(int i=2;i<=n;++i)
163     {
164         char temp[5];
165         int u;
166         sc("%d%s",&u,temp);
167         add(u,i,1<<(temp[0]-'a'));
168         add(i,u,1<<(temp[0]-'a'));
169     }
170     dfs(1,-1,1,0);
171     dfs2(1,-1,1);
172     for(int i=1;i<=n;++i)
173         pr("%d ",ans[i]);
174     return 0;
175 }
176 
177 /**************************************************************************************/