zcmimi's blog
avatar
zc
2020-04-26 16:20:00
  • 本文总阅读量
查看原题

点击跳转

两次dfs即可

第一次dfs:

计算出每个点的子树,包含这个点,答案最大是多少

显然S_x=v_x+\sum\limits_{y\in son_x} [S_y>0]S_y

(若x为黑点v_x=-1,否则v_x=1)

第二次dfs:

通过x的父亲的答案来计算出x的答案

如果x目前的答案>0,则从x的答案减去x目前的答案

如果这个结果>0,那么x的答案加上这个结果

感觉直接看代码可能更直观

#include<bits/stdc++.h>
#define gc getchar()
#define fur(i,x,y) for(int i=x;i<=y;++i)
void in(int &x){x=0;char c;bool f=0;for(c=gc;c<'0'||'9'<c;c=gc)f^=c=='-';for(x=c-48,c=gc;'0'<=c&&c<='9';x=x*10+c-48,c=gc);if(f)x=-x;}
const int N=200011;
int n,cnt,head[N],s[N];
struct edge{int to,nxt;}e[N<<1];
void add(int x,int y){e[++cnt].to=y,e[cnt].nxt=head[x];head[x]=cnt;}
void dfs(int x,int f){
    for(int i=head[x],to;to=e[i].to,i;i=e[i].nxt)
        if(to^f){dfs(to,x);if(s[to]>0)s[x]+=s[to];}
}
void up(int x,int f){
    int t=s[f];if(s[x]>0)t-=s[x];
    if(t>0)s[x]+=t;
    for(int i=head[x],to;to=e[i].to,i;i=e[i].nxt)
        if(to^f)up(to,x);
}
int main(){
    in(n);
    int x,y;
    fur(i,1,n)in(x),s[i]=x?1:-1;
    fur(i,1,n-1)in(x),in(y),add(x,y),add(y,x);
    dfs(1,0);up(1,0);
    fur(i,1,n)printf("%d ",s[i]);
}
LG CF1324F Maximum White Subtree
comment评论
Search
search