2 条题解
-
0
// 树形DP O(n) #include<bits/stdc++.h> using namespace std; int read(){ int x=0,f=1;char c=getchar(); while(c>'9'||c<'0'){if(c=='-') f=-1;c=getchar();} while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();} return x*f; } const int N=200005; int n,T,ans; vector<int> e[N]; int d[N],f[N],g[N],h[N]; int D[N][3],S[N][3]; void upd(int u,int v,int dv){ if(dv>=D[u][0]){ D[u][2]=D[u][1];S[u][2]=S[u][1]; D[u][1]=D[u][0];S[u][1]=S[u][0]; D[u][0]=dv;S[u][0]=v; } else if(dv>=D[u][1]){ D[u][2]=D[u][1];S[u][2]=S[u][1]; D[u][1]=dv;S[u][1]=v; } else if(dv>D[u][2])D[u][2]=dv,S[u][2]=v; } void dfs(int u){ int f1=0,f2=0; for(int v:e[u]){ dfs(v); d[u]=max(d[u],d[v]+1); upd(u,v,d[v]); f[u]=max(f[u],f[v]); g[u]=max(g[u],g[v]+1); h[u]=max(h[u],h[v]); if(f[v]>f1) f2=f1,f1=f[v]; else if(f[v]>f2) f2=f[v]; } f[u]=max(f[u],D[u][0]+D[u][1]+2); h[u]=max(h[u],f1+f2); for(int v:e[u]){ g[u]=max(g[u],f[v]+(S[u][0]==v?D[u][1]:D[u][0])+1); int res=0,cnt=0; if(S[u][0]!=v) res+=D[u][0],cnt++; if(S[u][1]!=v) res+=D[u][1],cnt++; if(cnt<2&&S[u][2]!=v) res+=D[u][2]; h[u]=max(h[u],f[v]+res+2); h[u]=max(h[u],g[v]+(S[u][0]==v?D[u][1]:D[u][0])+2); } } int main(){ T=read(); while(T--){ n=read(); for(int i=1;i<=n;i++){ e[i].clear(); for(int j=0;j<=2;j++)D[i][j]=-1,S[i][j]=0; d[i]=f[i]=h[i]=0; g[i]=-1; } for(int i=2,x;i<=n;i++) x=read(),e[x].push_back(i); dfs(1); int mx1=-1,mx2=-1; ans=0; for(int i:e[1]){ if(f[i]>mx1) mx2=mx1,mx1=f[i]; else if(f[i]>mx2) mx2=f[i]; ans=max(ans,h[i]+2); } ans=max(ans,mx1+mx2+2); if(n==2) ans=1; printf("%d\n",ans); } return 0; }#include<bits/stdc++.h> using namespace std; typedef unsigned long long LL; int N[]={0,10,20,90,200000,200000}; int T[]={0,10000,10000,10000,10000,15}; int M[]={0,3,3,4,3,7}; char infile[100]; char outfile[100]; char cmd[100]; int random(int l,int r)//产生一个范围[l,r]的数 { return (LL)rand()*rand()*rand()%(r-l+1)+l; //rand()是系统函数，只能产生[0,32767]的数 //rand()*rand()==1,073,676,289 } int main() { srand(time(0)); for(int t=1;t<=5;t++)for(int mi=1;mi<=M[t];mi++) { sprintf(infile,"a%d%d.in",t,mi); sprintf(outfile,"a%d%d.out",t,mi); freopen(infile,"w",stdout); printf("%d\n",T[t]); while(T[t]--){ int n=N[t]; printf("%d\n",n); for(int i=2;i<=n;i++){ int x=random(1,i-1); printf("%d ",x); } printf("\n"); } fclose(stdout); // 假设 std 在当前目录 sprintf(cmd,"std.exe < %s > %s",infile,outfile); int result = system(cmd); if(result != 0) { fprintf(stderr,"运行 std 失败，文件: %s\n", infile); } else { fprintf(stderr,"正在制造第 %d 组数据\n",t); } } } -
0
E93 树形DP+树的直径 P10794『SpOI - R1』架子鼓可以站 C
// 树形DP O(n) #include<bits/stdc++.h> using namespace std; int read(){ int x=0,f=1;char c=getchar(); while(c>'9'||c<'0'){if(c=='-') f=-1;c=getchar();} while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();} return x*f; } const int N=200005; int n,T,ans; vector<int> e[N]; int d[N],f[N],g[N],h[N]; int D[N][3],S[N][3]; void upd(int u,int v,int dv){ if(dv>=D[u][0]){ D[u][2]=D[u][1];S[u][2]=S[u][1]; D[u][1]=D[u][0];S[u][1]=S[u][0]; D[u][0]=dv;S[u][0]=v; } else if(dv>=D[u][1]){ D[u][2]=D[u][1];S[u][2]=S[u][1]; D[u][1]=dv;S[u][1]=v; } else if(dv>D[u][2])D[u][2]=dv,S[u][2]=v; } void dfs(int u){ int f1=0,f2=0; for(int v:e[u]){ dfs(v); d[u]=max(d[u],d[v]+1); upd(u,v,d[v]); f[u]=max(f[u],f[v]); g[u]=max(g[u],g[v]+1); h[u]=max(h[u],h[v]); if(f[v]>f1) f2=f1,f1=f[v]; else if(f[v]>f2) f2=f[v]; } f[u]=max(f[u],D[u][0]+D[u][1]+2); h[u]=max(h[u],f1+f2); for(int v:e[u]){ g[u]=max(g[u],f[v]+(S[u][0]==v?D[u][1]:D[u][0])+1); int res=0,cnt=0; if(S[u][0]!=v) res+=D[u][0],cnt++; if(S[u][1]!=v) res+=D[u][1],cnt++; if(cnt<2&&S[u][2]!=v) res+=D[u][2]; h[u]=max(h[u],f[v]+res+2); h[u]=max(h[u],g[v]+(S[u][0]==v?D[u][1]:D[u][0])+2); } } int main(){ T=read(); while(T--){ n=read(); for(int i=1;i<=n;i++){ e[i].clear(); for(int j=0;j<=2;j++)D[i][j]=-1,S[i][j]=0; d[i]=f[i]=h[i]=0; g[i]=-1; } for(int i=2,x;i<=n;i++) x=read(),e[x].push_back(i); dfs(1); int mx1=-1,mx2=-1; ans=0; for(int i:e[1]){ if(f[i]>mx1) mx2=mx1,mx1=f[i]; else if(f[i]>mx2) mx2=f[i]; ans=max(ans,h[i]+2); } ans=max(ans,mx1+mx2+2); if(n==2) ans=1; printf("%d\n",ans); } }
- 1
