zcmimi's blog
查看原题

点击跳转

f_{i,j}表示前i个点,第i个点的覆盖状态为j(j8位二进制数)

#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 CF1313D Happy New Year
comment评论
Search
search