头部背景图片
Decaku 's Blog |
Decaku 's Blog |

CF #627 F Maximum White Subtree

$题意:有一个无根树,每个结点都是黑白两种颜色之一,对于每个 \\
结点i,输出包含i的连通块里白色结点数减黑色结点数最大值。$


$首先无根树转有根树,然后树dp,设dp[u]是在u的子树里且包含u的 \\
连通块最大值,fdp[u]是除了u的子树且包含u的父亲的连通块最大值 \\
然后dp[u]从下向上转移,fdp[u]从上向下转移就行了。细节需要自己 \\
扣一下。$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include<bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false);cin.tie(0);
#define pii pair<ll,ll>
#define F first
#define S second
#define pb push_back
#define mp make_pair
#define rep(i,a,b) for(ll i=a;i<=(ll)b;++i)
#define per(i,a,b) for(ll i=a;i>=(ll)b;--i)
#define ll long long
#define lowbit(x) ((x)&(-x))

const int maxn=2e5+5;
int a[maxn],dp[maxn],fdp[maxn],ans[maxn];
vector<int>g[maxn];

void dfs1(int u,int f)
{
dp[u] = a[u]?1:-1;
for(auto v:g[u])
{
if(v==f) continue;
dfs1(v,u);
if(dp[v]>0) dp[u] += dp[v];
}
}

void dfs2(int u,int f)
{
int sum = 0;
for(auto v:g[u])
{
if(v==f) continue;
if(dp[v]>0) sum += dp[v];
}
for(auto v:g[u])
{
if(v==f) continue;
int tem = sum;
if(dp[v]>0) tem -= dp[v];
fdp[v] = a[u]?1:-1;
fdp[v] = max(fdp[v],fdp[v]+fdp[u]);
// fdp[v] = fdp[u];
// if(a[u]==1) fdp[v] += 1;
// else fdp[v] -= 1;
if(tem>0) fdp[v] += tem;
}
for(auto v:g[u])
{
if(v==f) continue;
dfs2(v,u);
}
}


int main()
{
int n; cin>>n;
rep(i,1,n) cin>>a[i];
rep(i,1,n-1){
int u,v; cin>>u>>v;
g[u].pb(v); g[v].pb(u);
}
dfs1(1,0);
dfs2(1,0);
rep(i,1,n){
ans[i] = dp[i];
if(fdp[i]>0) ans[i] += fdp[i];
}
rep(i,1,n) cout<<ans[i]<<" ";
cout<<"\n";
//rep(i,1,n) cout<<dp[i]<<" ";
//cout<<endl;
//rep(i,1,n) cout<<i<<":"<<fdp[i]<<endl;
}
avatar Decaku 菜菜菜