锐客网

  1. 首页 > it技术 > >

[codeforces 1388C] Uncle Bogdan and Country Happiness 树的遍历+树的子树节点数量的变形

codeforces

Codeforces Round #660 (Div. 2)参与排名人数13591
[codeforces 1388C]Uncle Bogdan and Country Happiness树的遍历+树的子树节点数量的变形
总目录详见https://blog.csdn.net/mrcrack/article/details/103564004
在线测评地址https://codeforces.com/contest/1388/problem/C

Problem Lang Verdict Time Memory
C - Uncle Bogdan and Country Happiness GNU C++17 Accepted 140 ms 12500 KB
该题开创了先河：第一次独立运用树的性质，解决树的问题，原来对树的问题，一团浆糊，慢慢有了感觉。
题目大意：n个人都从首都(城市1)出发,以最短路径回到归属的城市，每个人经过一个城市，好心情可以还是好心情，好心情也可以变成坏心情，但是坏心情不能变成好心情，坏心情只能一直是坏心情了。给出经过各个城市的人员的心情统计，问这种情况是否能发生，若能，输出YES,若不能，输出NO.
基本思路：吃透样例是关键。
经过该城市的总人数可以通过树的子树节点数量的变形进行计算。
【[codeforces 1388C] Uncle Bogdan and Country Happiness 树的遍历+树的子树节点数量的变形】[codeforces 1388C] Uncle Bogdan and Country Happiness 树的遍历+树的子树节点数量的变形
文章图片


[codeforces 1388C] Uncle Bogdan and Country Happiness 树的遍历+树的子树节点数量的变形
文章图片

Input: 2 4 4 1 1 1 1 4 1 -3 -1 1 2 1 3 1 4 3 13 3 3 7 13 1 4 1 2 1 3 Output: NO NO

[codeforces 1388C] Uncle Bogdan and Country Happiness 树的遍历+树的子树节点数量的变形
文章图片


[codeforces 1388C] Uncle Bogdan and Country Happiness 树的遍历+树的子树节点数量的变形
文章图片

Input: 2 7 4 1 0 1 1 0 1 0 4 0 0 -1 0 -1 0 1 2 1 3 1 4 3 5 3 6 3 7 5 11 1 2 5 2 1 -11 -2 -6 -2 -1 1 2 1 3 1 4 3 5 Output: YES YES

AC代码如下：
#include #define maxn 200010 int h[maxn],head[maxn],tot,num1[maxn],num2[maxn],num3[maxn],flag,n,m,num4[maxn],f[maxn]; struct node{ int to,next; }e[maxn<<1]; void add_edge(int u,int v){//临界表 tot++,e[tot].to=v,e[tot].next=head[u],head[u]=tot; } void dfs1(int u,int fa){//计算经过每个城市的人数，确认城市间的父子关系 int v,b; f[u]=fa; for(b=head[u]; b; b=e[b].next){ v=e[b].to; if(v==fa)continue; //若是父节点，跳过 dfs1(v,u); num1[u]+=num1[v]; //num1[u]表示经过城市u的所有人数 } } void count(){ int a,u,b,v; for(u=1; u<=n; u++){ a=num1[u]+h[u]; if(a%2){flag=1; return; }//a若是奇数，无效 num2[u]=a/2; //num2[u]表示经过城市u的好心情人数(包括城市u) num3[u]=num1[u]-num2[u]; //num3[u]表示经过城市u的坏心情人数(包括城市u) if(num2[u]<0||num3[u]<0){flag=1; return; }//负数，无效 } for(u=1; u<=n; u++) for(b=head[u]; b; b=e[b].next){ v=e[b].to; if(v!=f[u])num4[u]+=num2[v]; //num4[u]表示以城市u为父节点，直接相连的字节点城市的好心情人数(不包括城市u) } for(u=1; u<=n; u++) if(num2[u]


    推荐阅读


    上一篇：[codeforces 1385E] Directing Edges 变形的拓扑排序

    下一篇：javaFX配置到myeclipse，并zzJavaFX和Java之间的互操作性