题目描述
520马上就要到了，丁丁妹在思考送自己的室友什么礼物能够彰显她深深的室友之爱。
由于丁丁妹最近沉迷于种树，于是她决定送一颗摇钱树。
具体而言，这颗摇钱树有n个节点，编号为1~n，根节点编号为1。
丁丁妹在每个节点上都挂了一些钱，每次摇一个节点，以该节点为根的子树上的钱全部都会掉下来。
现在丁丁妹很好奇摇不同的节点会掉下多少钱来，请你来帮助她解决这个问题。
输入描述
单组数据，第一行为两个整数n,m，代表摇钱树的节点个数，以及询问个数。
接下来一行有n个数字，表示丁丁妹在每个节点上挂的钱数。
接下来n−1行，每行两个数字x,y，描述了摇钱树上的一条边的两个端点。
接下来mm行，每行一个数字x，代表询问摇以x为根的子树能掉下来多少钱。
数据保证：
1.m≤n≤10000
2.每个节点挂的钱数≤1000
输出描述
输出m行，每行一个数字C，对应一个询问的答案。
样例输入
3 3
1 2 3
2 1
1 3
1
2
3
样例输出
6
2
3
分析
我的办法可能利用了一点题目的小漏洞，通过输入整理边上的两个节点，使父亲节点在前，让后通过递归获取结果。也可以通过线段树来做，但我不会。
代码实现
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
int n,m;
int money[10005];
int side[10005][2];
int tag[10005];
int ans[10005];
int dfs(int cur)
{
if(ans[cur]!=0)
return ans[cur];
int sum=0;
for(int i=1; i<=n; i++)
{
if(side[i][0]==cur)
{
sum+=dfs(side[i][1]);
}
}
ans[cur]=sum+money[cur];
return ans[cur];
}
int main()
{
cin>>n>>m;
for(int i=1; i<=n; i++)
{
scanf("%d",&money[i]);
}
tag[1]=1;
for(int i=1; i<n; i++)
{
scanf("%d %d",&side[i][0],&side[i][1]);
if(tag[side[i][0]]>0)
{
tag[side[i][1]]++;
}
else if(tag[side[i][1]]>0)
{
int temp=side[i][0];
side[i][0]=side[i][1];
side[i][1]=temp;
tag[side[i][1]]++;
}
}
while(m-->0)
{
int start;
scanf("%d",&start);
printf("%dn",dfs(start));
}
}
cpp
运行
