0分求调
查看原帖
0分求调
922019
xiaoniu142857楼主2024/10/12 21:29

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;
}
2024/10/12 21:29
加载中...