傳送門

文章目錄

• 題意：
• 思路：

題意：

思路：

據(jù)說(shuō)是樹(shù)啟的壓軸題。
先觀察題意，字符有$1?22$中，為什么不是$1?26$個(gè)？顯然他就是讓你狀壓的。我們考慮將每條路徑上字符狀壓成$state$，讓后從$1$開(kāi)始遍歷，記從$1$到$i$的路徑上的$state$為$dis[i]$。
再觀察一下回文的性質(zhì)，回文中奇數(shù)個(gè)字母最多只有一個(gè)，如果兩條路徑能構(gòu)成回文，那么他們的$dis[i]xordis[j]$最多只有$23$種情況，即$00...00,10...00,01...00,...,00...01$。那么我們就可以每次都$check$一下是否存在$dis[j]=dis[i]xor23種情況$。又因?yàn)槊總€(gè)狀態(tài)有可能有多個(gè)$depth$，讓后我就蠢的對(duì)每個(gè)狀態(tài)開(kāi)了個(gè)$multiset$，先不說(shuō)內(nèi)存爆沒(méi)爆(我卡了下內(nèi)存沒(méi)爆)，復(fù)雜度高達(dá)$O(23nlo{g}^{2}n)$，我也不知道我怎么想的，就這么寫(xiě)了寫(xiě)交了， 結(jié)局也比較顯然，$TLEtext10$了(逃。
顯然這個(gè)題可以不用$multiset$，記$mx[i]$為狀態(tài)是$i$的最大深度，根據(jù)$dsu$的特性，每次我們清空的時(shí)候都將$mx[i]$重置為$0$，每次算的時(shí)候就貪心的用$mx[i]$即可。相信大部分第一反應(yīng)都是這樣做，但是可能考慮到直接置為$0$可能會(huì)影響到重兒子導(dǎo)致答案錯(cuò)誤就放棄了這種想法。那么為什么這樣是正確的呢？因?yàn)?span id="ze8trgl8bvbq" class="katex--inline">$dsu$每次清空的時(shí)候都是清空非重兒子的子樹(shù)，而且是清空之后才遍歷重兒子，所以不會(huì)影響到重兒子的值。還是要對(duì)$dsu$的遍歷順序理解的比較深刻才能想到。

//#pragma GCC optimize(2) #include<cstdio> #include<iostream> #include<string> #include<cstring> #include<map> #include<cmath> #include<cctype> #include<vector> #include<set> #include<queue> #include<algorithm> #include<sstream> #include<ctime> #include<cstdlib> #define X first #define Y second #define L (u<<1) #define R (u<<1|1) #define pb push_back #define mk make_pair #define Mid (tr[u].l+tr[u].r>>1) #define Len(u) (tr[u].r-tr[u].l+1) #define random(a,b) ((a)+rand()%((b)-(a)+1)) #define db puts("---") using namespace std;//void rd_cre() { freopen("d://dp//data.txt","w",stdout); srand(time(NULL)); } //void rd_ac() { freopen("d://dp//data.txt","r",stdin); freopen("d://dp//AC.txt","w",stdout); } //void rd_wa() { freopen("d://dp//data.txt","r",stdin); freopen("d://dp//WA.txt","w",stdout); }typedef long long LL; typedef unsigned long long ULL; typedef pair<int,int> PII;const int N=500010,M=N*2,mod=1e9+7,INF=0x3f3f3f3f; const double eps=1e-6;int n; int e[M],ne[M],w[M],h[N],idx; int depth[N],son[N],se[N],dis[N]; int ans[N],len,mx[(1<<23)];void add(int a,int b,int c) {e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++; }void dfs_son(int u,int fa,int state) {dis[u]=state; se[u]=1;depth[u]=depth[fa]+1;for(int i=h[u];~i;i=ne[i]){int x=e[i];if(x==fa) continue;dfs_son(x,u,state^(1<<w[i]));se[u]+=se[x];if(se[x]>se[son[u]]) son[u]=x;} }void solve(int u,int fa,int rt) {int y=dis[u];if(mx[y]!=0) ans[rt]=max(ans[rt],depth[u]+mx[y]-2*depth[rt]);for(int i=0;i<22;i++){y=dis[u]^(1<<i);if(mx[y]!=0) ans[rt]=max(ans[rt],depth[u]+mx[y]-2*depth[rt]);}for(int i=h[u];~i;i=ne[i]){int x=e[i];if(x==fa) continue;solve(x,u,rt);} }void update(int u,int fa,int tag) {if(tag==1) mx[dis[u]]=max(mx[dis[u]],depth[u]);else mx[dis[u]]=0;for(int i=h[u];~i;i=ne[i]){int x=e[i];if(x==fa) continue;update(x,u,tag);} }void dfs(int u,int fa,int op) {for(int i=h[u];~i;i=ne[i]){int x=e[i];if(x==fa||x==son[u]) continue;dfs(x,u,0); ans[u]=max(ans[u],ans[x]);}if(son[u]) dfs(son[u],u,1),ans[u]=max(ans[u],ans[son[u]]);if(son[u]){if(mx[dis[u]]) ans[u]=max(ans[u],mx[dis[u]]-depth[u]);for(int i=0;i<22;i++) if(mx[dis[u]^(1<<i)]) ans[u]=max(ans[u],mx[dis[u]^(1<<i)]-depth[u]);}mx[dis[u]]=max(mx[dis[u]],depth[u]);for(int i=h[u];~i;i=ne[i]){int x=e[i];if(x==fa||x==son[u]) continue;solve(x,u,u); update(x,u,1);}if(!op) update(u,fa,-1); }int main() { // ios::sync_with_stdio(false); // cin.tie(0);scanf("%d",&n); idx=0;memset(h,-1,sizeof(h));for(int i=2;i<=n;i++){int a; char b[2];scanf("%d%s",&a,b);add(a,i,(int)(b[0]-'a'));}dfs_son(1,0,0);dfs(1,0,1);for(int i=1;i<=n;i++) printf("%d ",ans[i]);puts("");return 0; } /**/

貼個(gè)$TLE$的代碼記錄一下我的蜜汁操作

//#pragma GCC optimize(2) #include<cstdio> #include<iostream> #include<string> #include<cstring> #include<map> #include<cmath> #include<cctype> #include<vector> #include<set> #include<queue> #include<algorithm> #include<sstream> #include<ctime> #include<cstdlib> #define X first #define Y second #define L (u<<1) #define R (u<<1|1) #define pb push_back #define mk make_pair #define Mid (tr[u].l+tr[u].r>>1) #define Len(u) (tr[u].r-tr[u].l+1) #define random(a,b) ((a)+rand()%((b)-(a)+1)) #define db puts("---") using namespace std;//void rd_cre() { freopen("d://dp//data.txt","w",stdout); srand(time(NULL)); } //void rd_ac() { freopen("d://dp//data.txt","r",stdin); freopen("d://dp//AC.txt","w",stdout); } //void rd_wa() { freopen("d://dp//data.txt","r",stdin); freopen("d://dp//WA.txt","w",stdout); }typedef long long LL; typedef unsigned long long ULL; typedef pair<int,int> PII;const int N=500010,M=N*2,mod=1e9+7,INF=0x3f3f3f3f; const double eps=1e-6;int n; int e[M],ne[M],w[M],h[N],idx; int depth[N],son[N],se[N],dis[N]; int ans[N],len; multiset<int>s[(1<<23)];void add(int a,int b,int c) {e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++; }void dfs_son(int u,int fa,int state) {dis[u]=state; se[u]=1;depth[u]=depth[fa]+1;for(int i=h[u];~i;i=ne[i]){int x=e[i];if(x==fa) continue;dfs_son(x,u,state^(1<<w[i]));se[u]+=se[x];if(se[x]>se[son[u]]) son[u]=x;} }void solve(int u,int fa,int rt) {int y=dis[u];if(s[y].size()) len=max(len,depth[u]+(*s[y].rbegin())-2*depth[rt]);for(int i=0;i<22;i++){y=dis[u]^(1<<i);if(s[y].size()) len=max(len,depth[u]+(*s[y].rbegin())-2*depth[rt]);}for(int i=h[u];~i;i=ne[i]){int x=e[i];if(x==fa) continue;solve(x,u,rt);} }void update(int u,int fa,int tag) {if(tag==1) s[dis[u]].insert(depth[u]);else s[dis[u]].erase(s[dis[u]].find(depth[u]));for(int i=h[u];~i;i=ne[i]){int x=e[i];if(x==fa) continue;update(x,u,tag);} }void solve_son(int u,int fa,int rt) {if((dis[u]^dis[rt])==0) len=max(len,depth[u]-depth[rt]);for(int i=0;i<22;i++){int y=dis[u]^(1<<i);if(y!=dis[rt]) continue;len=max(len,depth[u]-depth[rt]);}for(int i=h[u];~i;i=ne[i]){int x=e[i];if(x==fa) continue;solve_son(x,u,rt);} }void dfs(int u,int fa,int op) {for(int i=h[u];~i;i=ne[i]){int x=e[i];if(x==fa||x==son[u]) continue;dfs(x,u,0);}if(son[u]) dfs(son[u],u,1);s[dis[u]].insert(depth[u]);if(son[u]) solve_son(son[u],u,u);for(int i=h[u];~i;i=ne[i]){int x=e[i];if(x==fa||x==son[u]) continue;solve(x,u,u); update(x,u,1);}ans[u]=len; len=0;if(!op) update(u,fa,-1),len=0; }void dfs_ans(int u,int fa) {for(int i=h[u];~i;i=ne[i]){int x=e[i];if(x==fa) continue;dfs_ans(x,u);ans[u]=max(ans[u],ans[x]);} }int main() { // ios::sync_with_stdio(false); // cin.tie(0);scanf("%d",&n); idx=0;memset(h,-1,sizeof(h));for(int i=2;i<=n;i++){int a; char b[2];scanf("%d%s",&a,b);add(a,i,(int)(b[0]-'a'));}dfs_son(1,0,0);dfs(1,0,1);dfs_ans(1,0);for(int i=1;i<=n;i++) printf("%d ",ans[i]);puts("");return 0; } /**/

總結(jié)

以上是生活随笔為你收集整理的CF741D Arpa’s letter-marked tree and Mehrdad’s Dokhtar-kosh paths 树启 + 状压的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。