题目
有一棵树，限制从每个点出发的次数最多为(c_i)，对于每个点i，求1到i的路径最多经过多少次边(,(nleq 40000))，保证每个点的(c)大于其入度
解法1
直接莽？拆点，中间连容量为(c_i)费用为0的边，点与点之间连容量为inf费用为1的边，从1到每个点i跑一次最大费用最大流即可
显然过不了本题数据
解法2
考虑树形DP解决这个网络流问题
递推解决问题？本题难点在于：确定递推顺序然后确定一个点的答案
由于每个点的(c)都大于其入度，那么从1开始一定可以将所有点走一遍回到1，先走这样的一条路；
然后如果一条边两端的点都还可以走，那么走一个环可以再多给答案+2，直到每条边两端都至少有1个点(c)值为0为止，容易发现这样走小圈的贪心对于(ans_1)是最优的
根节点的答案求出来了，于是考虑从父亲向儿子递推：
-
父亲的(c)值不为0，由父亲走到儿子，那么儿子的答案为父亲+1；（由于父亲最优所以儿子也不存在更优解）
-
父亲的(c)值为0，由于父亲的答案为终止在父亲节点的路径，那么这条路径不可能再回到儿子节点了，所以不能走这条儿子->父亲的边，将这条边退掉，儿子又有一次走的机会；此时如果儿子的儿子还可以走那就走一个小环，否则就不加
注意，由于上面的贪心已经使得一条边的两端至少有1个点(c)值为0，所以上面的分类讨论中，即使可以多走也只是1~2条边
Code
#include<bits/stdc++.h>
#define N 50005
#define Min(x,y) ((x)<(y)?(x):(y))
#define Max(x,y) ((x)>(y)?(x):(y))
using namespace std;
typedef long long ll;
int n,c[N],ans[N],g[N],now;
struct Edge
{
int next,to;
}edge[N<<1];int head[N],cnt=1;
void add_edge(int from,int to)
{
edge[++cnt].next=head[from];
edge[cnt].to=to;
head[from]=cnt;
}
template <class T>
void read(T &x)
{
char c; int sign=1;
while((c=getchar())>'9'||c<'0') if(c=='-') sign=-1; x=c-48;
while((c=getchar())>='0'&&c<='9') x=(x<<1)+(x<<3)+c-48; x*=sign;
}
void DFS(int rt,int fa)
{
for(int i=head[rt];i;i=edge[i].next)
{
int v=edge[i].to;
if(v==fa) continue;
DFS(v,rt);
int ct=Min(c[rt],c[v]);
c[rt]-=ct; c[v]-=ct;
now+=ct*2;
if(c[v]) g[rt]=v;
}
}
void dfs(int rt,int fa)
{
ans[rt]=now;
for(int i=head[rt];i;i=edge[i].next)
{
int v=edge[i].to;
if(v==fa) continue;
int flag=0;//回溯用
if(c[rt]>0) { --c[rt]; ++now; flag=1; }
else if(g[v]) { --c[g[v]]; ++now; flag=2; }
else { ++c[v]; --now; flag=3; }
dfs(v,rt);
if(flag==1) ++c[rt],--now;
if(flag==2) ++c[g[v]],--now;
if(flag==3) --c[v],++now;
}
}
int main()
{
read(n);
for(int i=1;i<=n;++i) read(c[i]);
for(int i=1;i<n;++i)
{
int x,y;
read(x);read(y);
++x;++y;
add_edge(x,y);
add_edge(y,x);
--c[x];--c[y];
now+=2;
}
DFS(1,0); dfs(1,0);
for(int i=1;i<=n;++i) printf("%d
",ans[i]);
return 0;
}