题目： 小美喜欢吃鸭舌。 有一个 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，但是逻辑总是出错，花出大把时间，最后时间不够了想打暴力，也写错了……思路主要是对于一个节点，找到它的所有儿子，每一个儿子又有自己对应的子树，就这样深搜到底。
代码： 30分暴搜（就是一个老鼠走迷宫，我代码能力太弱啦，居然打错）：
#include<iostream> #include<cstdio> #include<cstdlib> #include<cmath> #include<ctime> #include<cctype> #include<cstring> #include<string> #include<algorithm> using namespace std; const int N=100005; long long a[N]; int n,x; int first[N],next[N*2],go[N*2],tot=0; long long ans=0; inline void comb(int a,int b) { next[++tot]=first[a],first[a]=tot,go[tot]=b; next[++tot]=first[b],first[b]=tot,go[tot]=a; } inline void dfs(int now,long long tot) { if(tot!=0) a[now]--; if(now==x) ans=max(ans,tot); for(int e=first[now];e;e=next[e]) { int v=go[e]; if(a[v]==0) continue; dfs(v,tot+1); } a[now]++; } int main() { //freopen("tongue.in","r",stdin); //freopen("tongue.out","w",stdout); scanf("%d",&n); if(n<=5) { for(int i=1;i<=n;i++) cin>>a[i]; for(int i=1;i<n;i++) { int a,b; scanf("%d%d",&a,&b); comb(a,b); } scanf("%d",&x); dfs(x,0); cout<<ans<<endl; } return 0; }100分代码：
#include<iostream> #include<cstdio> #include<cstring> #include<string> #include<algorithm> #include<cmath> #include<queue> using namespace std; int getint() { int i=0,f=1;char c; for(c=getchar();(c<'0'||c>'9')&&c!='-';c=getchar()); if(c=='-')f=-1,c=getchar(); for(;c>='0'&&c<='9';c=getchar())i=(i<<3)+(i<<1)+c-'0'; return i*f; } const int N=2e5+5; int n,tot,root,len,a[N],size[N]; int first[N],next[N],to[N]; long long f[N],cnt[N],tmp[N]; void add(int x,int y) { next[++tot]=first[x],first[x]=tot,to[tot]=y; } bool cmp(const long long &a,const long long &b) { return a>b; } void dfs(int x,int fa) { for(int i=1;i<=len;i++)tmp[i]=0;//用来记录所有儿子子树能吃到的鸭舌 len=0; for(int e=first[x];e;e=next[e])//枚举每一条边 { int y=to[e]; if(a[y]&&y!=fa) { size[x]++;//记录有多少个儿子 a[y]--;//去了这条边，先吃掉一个鸭舌 if(a[y])dfs(y,x);//如果这个儿子还有鸭舌就继续搜索这个子树 cnt[x]+=a[y];//记录子树走完后这个儿子还剩多少鸭舌 tmp[++len]=f[y];//f记录走完这个子树能吃掉多少鸭舌，tmp是个临时数组，后面排序用的 f[x]+=f[y];//先把子树吃掉的鸭舌加到f[父亲] } } if(a[x]>=size[x])//如果a[x]>size[x]，说明可以把每个子树都走一遍 { f[x]+=2*size[x];//把走到每个需要消耗的鸭舌加进来 a[x]-=size[x];//a[x]失去size[x]个鸭舌 f[x]+=2*min(cnt[x],(long long)a[x]);//再加上min(父亲剩下的，所有儿子剩下的)，也就是最后在父亲和儿子之间不断来回走把其中一个吃完的过程 a[x]-=min(cnt[x],(long long)a[x]);//父亲又少了这么多鸭舌 } else//如果父亲的鸭舌量不够走完所有子树 { f[x]=2*a[x];//父亲的肯定要消耗完，因为来回，所以*2（这里f[x]已经重新赋值了，所以前面那个f[x]+=f[y]不会出bug） sort(tmp+1,tmp+len+1,cmp);//从大到小排所有子树能吃掉的 for(int i=1;i<=a[x];i++) f[x]+=tmp[i];//加上最多的那几个子树 a[x]=0;//父亲清零 } } int main() { freopen("tongue.in","r",stdin); freopen("tongue.out","w",stdout); int x,y; n=getint(); for(int i=1;i<=n;i++)a[i]=getint(); for(int i=1;i<n;i++) { x=getint(),y=getint(); add(x,y),add(y,x);//建边 } root=getint(); dfs(root,0); cout<<f[root]; return 0; }本题结。
