0分提交记录
和这篇题解思路几乎一样,但就是找不出问题
哪位大佬帮我调一下,非常感谢!
#include <cstdio>
#include <algorithm>
#define N 100005
#define NINF -1000000000
#define add(u,v) (to[++cnt]=(v),nxt[cnt]=hd[u],hd[u]=cnt)
#define repg(i,x) for(register int i(hd[x]);i;i=nxt[i])
using namespace std;
int c[N],hd[N],dp[N][2],to[N<<1],nxt[N<<1],cnt,ans;
// dp[i][j] 表示以i为根的子树中到i最远的j颜色的节点的距离(j是0或1)
void dfs(int u,int pa)
{
int wx1(NINF),argw1,wx2(NINF);
int bx1(NINF),argb1,bx2(NINF);
dp[u][c[u]]=0;
dp[u][!c[u]]=NINF;
repg(i,u)
{
int v(to[i]);
if(v==pa) continue;
dfs(v,u);
if(dp[v][0]>wx1) wx1=dp[v][0],argw1=v; // 更新白点最大距离
else if(dp[v][0]>wx2) wx2=dp[v][0]; // 白点次大距离
if(dp[v][1]>bx1) bx1=dp[v][1],argb1=v;
else if(dp[v][1]>bx2) bx2=dp[v][1];
}
dp[u][0]=max(dp[u][0],wx1+1);
dp[u][1]=max(dp[u][1],bx1+1);
ans=max(ans,dp[u][!c[u]]);
if(argw1==argb1) ans=max(ans,max(bx1+wx2,bx2+wx1)+2);
else ans=max(ans,bx1+wx1+2);
}
int main()
{
int n,x,y;
scanf("%d",&n);
for(int i(1);i<=n;++i) scanf("%1d",c+i);
for(int i(1);i<n;++i)
{
scanf("%d%d",&x,&y);
add(x,y),add(y,x);
}
dfs(1,0);
printf("%d",ans);
return 0;
}