题目背景

CF 77C

题目描述

小美喜欢吃鸭舌。
有一个 n 个点的树，每个节点 i ，第 i 个点上有 ai 个鸭舌。
小美一开始处于 x 号点。
每次小美可以选择一个与现在的点有边的点而且那个点还有鸭舌，那么小美会走到那个点并吃一个鸭舌。
要保证小美最后还是走到 x 号点。
问小美最多能吃几个鸭舌？

输入格式

输入第一行一个整数 n 。
接下来一行 n 个整数表示 ai 。
下面是 n-1 行每行两个整数表示一条边。
最后一行一个整数表示 x 。

输出格式

输出一行，一个整数，表示吃最多的鸭舌个数。

样例数据 1

输入　 [复制]

5 
1 3 1 3 2 
2 5 
3 4 
4 5 
1 5 
4

输出

6

样例数据 2

输入　 [复制]

3 
2 1 1 
3 2 
1 2 
3

输出

2

备注

【数据规模】
对于 30% 的数据：n≤5；ai≤5；
对于 100% 的数据：1≤n≤100000；0≤ai≤109；1≤x≤n。

树形dp，优先考虑走完一个子树，然后如果有剩余就和子节点来回走；另外我tm刚开始把储存dp【son】的队列弄成全局变量了啊···草，还是用vector好

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
const int N=;
long long a[N];
long long n,x;
long long first[N],next[N*],go[N*],tot=;
long long dp[N];
inline bool comp(long long a,long long b)
{
return a>b;
}
inline void comb(long long a,long long b)
{
next[++tot]=first[a],first[a]=tot,go[tot]=b;
next[++tot]=first[b],first[b]=tot,go[tot]=a;
}
inline void dfs(long long now,long long fa)
{
vectorque;
if(a[now]==) return;
long long totl=;
for(long long e=first[now];e;e=next[e])
{
if(go[e]==fa) continue;
dfs(go[e],now);
que.push_back(dp[go[e]]);
totl++;
}
sort(que.begin(),que.end(),comp);
a[now]--;
dp[now]=;
for(long long i=;i<totl;i++)
{
long long temp=que[i];
if (a[now]==) break;
if(temp!=)
{
dp[now]+=temp+;
a[now]--;
}
else break;
}
for(long long e=first[now];e;e=next[e])
{
if(go[e]==fa) continue;
long long temp=min(a[go[e]],a[now]);
a[now]-=temp;
dp[now]+=temp*;
}
}

int main()
{
//freopen("tongue.in","r",stdin);
//freopen("tongue.out","w",stdout);
scanf("%I64d",&n);
for(int i=;i<=n;i++)
scanf("%I64d",&a[i]);
for(int i=;i<n;i++)
{
long long a,b;
scanf("%I64d%I64d",&a,&b);
comb(a,b);
}
scanf("%I64d",&x);
a[x]++;
dfs(x,);
printf("%I64d",dp[x]-);
return ;
}