1 条题解

  • 0
    @ 2026-7-4 11:37:10

    //You may miss me deep down
    #include <cstdio>
    #include <iostream>
    using namespace std;
    const int M = 200005;
    const int inf = 0x3f3f3f3f;
    int read()
    {
    	int x=0,f=1;char c;
    	while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;}
    	while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
    	return x*f;
    }
    int n,tot,f[M],mx[M],se[M],d[M],sz[M];char s[M]; 
    struct edge{int v,next;}e[M<<1];long long ans;
    void dfs1(int u,int fa)
    {
    	if(s[u]=='1') d[u]=0,sz[u]=1;
    	else d[u]=inf;
    	for(int i=f[u];i;i=e[i].next)
    	{
    		int v=e[i].v;
    		if(v==fa) continue;
    		dfs1(v,u);sz[u]+=sz[v];
    		if(mx[v]+1>mx[u]) se[u]=mx[u],mx[u]=mx[v]+1;
    		else if(mx[v]+1>se[u]) se[u]=mx[v]+1;
    		if(sz[v]) d[u]=min(d[u],mx[v]+1);
    	}
    }
    void dfs2(int u,int fa)
    {
    	int up=min(se[u]+1,mx[u]-1);
    	if(d[u]<=up) ans+=up-d[u]+1;
    	for(int i=f[u];i;i=e[i].next)
    	{
    		int v=e[i].v;
    		if(v==fa) continue;
    		int t=(mx[v]+1==mx[u])?se[u]:mx[u];t++;
    		if(t>mx[v]) se[v]=mx[v],mx[v]=t;
    		else if(t>se[v]) se[v]=t;
    		if(sz[1]-sz[v]) d[v]=min(d[v],t);
    		dfs2(v,u);
    	}
    }
    signed main()
    {
    	n=read();
    	for(int i=1;i<n;i++)
    	{
    		int u=read(),v=read();
    		e[++tot]=edge{v,f[u]},f[u]=tot;
    		e[++tot]=edge{u,f[v]},f[v]=tot;
    	}
    	scanf("%s",s+1);
    	dfs1(1,0);dfs2(1,0);
    	printf("%lld\n",ans+1);
    }
    
    
    • 1

    信息

    ID
    8763
    时间
    2000ms
    内存
    256MiB
    难度
    10
    标签
    递交数
    2
    已通过
    1
    上传者