摇钱树（算法题）

题目描述

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)			//如果这个节点被记录过了，那他是父亲节点，让他排在前面，也许这是一个 BUG ，被我利用了 {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("%d\n",dfs(start));}
}