湛江网站建设哪家优惠多,临沂房产和房建设局网站双和,上海建筑设计研究院有限公司,cms网站管理系统题目大意
给出一颗 n n n个节点的无根树#xff0c;每个节点有一个颜色 a u a_u au#xff0c;如果 a u 0 a_u0 au0则为黑色#xff0c;否则为白色。
对于每个节点 u u u#xff0c;选出一个包含 u u u的联通子图#xff0c;设子图中白点个数为 c n t 1 cnt_1 cnt1…题目大意
给出一颗 n n n个节点的无根树每个节点有一个颜色 a u a_u au如果 a u 0 a_u0 au0则为黑色否则为白色。
对于每个节点 u u u选出一个包含 u u u的联通子图设子图中白点个数为 c n t 1 cnt_1 cnt1黑点个数为 c n t 2 cnt_2 cnt2输出 c n t 1 − c n t 2 cnt1-cnt_2 cnt1−cnt2的最大值。 1 ≤ n ≤ 2 ∗ 1 0 5 , 0 ≤ a u ≤ 1 1 \leq n \leq 2*10^5,0 \leq a_u \leq 1 1≤n≤2∗105,0≤au≤1。
题目思路
先以 1 1 1为根预处理出每个点的子树中 c n t 1 − c n t 2 cnt_1-cnt_2 cnt1−cnt2的最大值。
然后进行换根 d p dp dp。
当你把根从 u u u转移到 v v v时 f 2 v max ( f 2 u f 1 u − m a x ( f 1 v , 0 ) , 0 ) f2_v \max(f2_uf1_u-max(f1_v,0),0) f2vmax(f2uf1u−max(f1v,0),0)。 f 1 f1 f1就是上面预处理的数组 f 2 f_2 f2就是每个点子树外 c n t 1 − c n t 2 cnt_1-cnt_2 cnt1−cnt2的最大值。
因为只有根是必选的所以其他值需要跟 0 0 0取 m a x max max。
具体实现参考代码。
#includebits/stdc.h
using namespace std;
const int N20000010;
int n,a[N],f1[N],f2[N];
int head[N1],nxt[N1],to[N1],tot0;
void add(int u,int v)
{to[tot]v;nxt[tot]head[u];head[u]tot;
}
int read()
{int s0,w1;char chgetchar();while(ch0||ch9){if(ch-)w-1;chgetchar();} while(ch0ch9)ss*10(ch-0),chgetchar();return s*w;
}
void dfs1(int u,int fa)
{if(a[u])f1[u]1;else f1[u]-1;for(int ihead[u];i;inxt[i]){int vto[i];if(vfa)continue;dfs1(v,u);f1[u]max(f1[v],0);}
}
void dfs2(int u,int fa)
{for(int ihead[u];i;inxt[i]){int vto[i];if(vfa)continue;f2[v]max(f2[u]f1[u]-max(f1[v],0),0);dfs2(v,u);}
}
int main()
{nread();for(int i1;in;i)a[i]read();for(int i1;in-1;i){int uread(),vread();add(u,v);add(v,u);} dfs1(1,1);dfs2(1,1);for(int i1;in;i)printf(%d ,f1[i]f2[i]);return 0;
}
