刷题总结——鸭舌（ssoi）

题目：

题目背景

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<iostream>

#include<cstdio>

#include<cstdlib>

#include<cmath>

#include<ctime>

#include<cctype>

#include<cstring>

#include<string>

#include<algorithm>

#include<vector>

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)

{

  vector<long long>que;

  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 ;

}

巴特西