1 条题解
-
0

//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
- 上传者