看到这道题第一眼是什么？
网络流！exciting！
大佬们以光速复制敲好板子，用3毫秒想出了如何建模，打好程序，看眼数据范围……
笑容渐渐消失.jpg
什么，还有我预流推进解决不了的卡常网络流？
还真搞不定
再仔细看一眼：N个星球，N-1条双向时空隧道，任意两点联通
——这是树！
树上网络流不行，那么……还有什么算法可以解决这类问题……
——树上DP！
好了怎么DP也是一个问题啊
先看一句话：
每个星球的H_iHi大于等于与该星球直接相连的星球数（即度数）。
什么鬼？为什么会有这种毒瘤玩意儿？
其实ta给我们提供了一个很关键的信息：
由于有Hi>=i的度数，那么可以想象在最坏情况下（比如所有Hi=i的度数），答案至少是根节点走过所有点之后回到根节点，然后去掉一个点i到根节点的那些路径。
——来自https://blog.csdn.net/lych_cys/article/details/51062609
那么感性一下，答案大概就是根节点回到根节点的最大流量，使得没有一条边e(u,v)，u和v的可出发次数都>0。
分三种情况讨论：
- 还可以从x处出发，总流量++，cnt[x]--
- y而儿子中存在一个点p的可出发次数>0，那么可以让y->x的流量-1，然后y->p流量+1，p->y流量+1，p的可出发次数-1；
- 否则没有办法到达y，那么只能让y->x的边退流，同时y的可出发次数+1。
——仍然来自https://blog.csdn.net/lych_cys/article/details/51062609
那么……
这就很显然了，代码就不防了（被泼硫酸
#include#include #include #include using namespace std;/*inline void read(int &x){ x=0; int f=1; char ch=getchar(); while(ch<'0'||ch>'9') { if(ch=='-') { f=-1; } ch=getchar(); } while(ch<='9'&&ch>='0') { x=(x<<3)+(x<<1)+ch-'0'; ch=getchar(); } x*=f;}*/struct note{ int next; int t;};note e[200010];int head[50010],ind[50010];int n;int cnt;int flag[50010],ans[50010],g[50010];int flow;inline void add(int x,int y){ e[++cnt].t=y; e[cnt].next=head[x]; head[x]=cnt; ind[y]--;}void dfs(int x,int fa){ for(int i=head[x];i+1;i=e[i].next) { int p=e[i].t; if(p==fa) { continue; } dfs(p,x); int val=min(ind[p],ind[x]); ind[x]-=val; ind[p]-=val; flow+=val<<1; if(ind[p]) { g[x]=p; } }}void solve(int x,int fa){ ans[x]=flow; for(int i=head[x];i+1;i=e[i].next) { int p=e[i].t; if(p==fa) { continue; } if(ind[x]) { ind[x]--; flow++; flag[x]=0; } else if(g[p]) { ind[g[p]]--; flow++; flag[x]=1; } else { ind[p]++; flow--; flag[x]=2; } solve(p,x); if(!flag[x]) { ind[x]++; flow--; } else if(flag[x]==1) { ind[g[p]]++; flow--; } else { ind[p]--; flow++; } }}int main(){ memset(head,-1,sizeof(head)); scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%d",&ind[i]); } for(int i=1;i