题干：
在星际争霸(StarCraft)中，有3个种族。对于任意一个种族，他们的建筑建造都是有一个顺序的。这个顺序正好是一个树形结构，我们称之为"科技树"(Technology tree)。
在科技树中，只有一个建筑是不需要前置建筑的，我们把这个建筑的编号设为1。其他的建筑，有且仅有一个前置建筑。
比如建筑2的前置建筑为建筑1，意思是只有先建造了建筑1，才能建造建筑2。
一个种族有n个建筑，建筑1没有前置建筑，建筑i(2≤i≤n)的前置建筑为f。每个建筑的建造都需要费用，建筑i(1≤i≤n)的建造花费为a晶体矿和b高能瓦斯。
现在tokitsukaze想知道，如果想要建造建筑x，总共需要消耗多少晶体矿和高能瓦斯。
输入描述:
第一行包含一个T(T≤10)，表示T组数据。
对于每组数据：
第一行包含两个正整数n，q(1≤n,q≤20000)，表示有n个建筑和q次查询。
接下来n行，每行包含两个整数a,b(0≤a,b≤300)，表示建造建筑i需要花费a晶体矿和b高能瓦斯。
接下来一行，包含n-1个正整数f(1≤f≤n)。第i个(1≤i＜n)正整数fi(1≤fi＜i)表示建筑i+1的前置建筑为fi。
接下来q行，每行包含一个正整数x，表示询问。 输出描述:
对于每个询问，输出一行，包含两个整数c,d(用空格隔开)，表示如果想要建造建筑x，总共需要消耗c晶体矿和d高能瓦斯。
示例1
输入
1
4 4
1 5
10 100
200 50
66 88
1 1 2
1
2
3
4 输出
1 5
11 105
201 55
77 193 说明
第一组样例：
如果想要建造建筑1，总共需要消耗1晶体矿和5高能瓦斯。
如果想要建造建筑2，需要先建造建筑1，总共需要消耗1+10晶体矿和5+100高能瓦斯。
如果想要建造建筑3，需要先建造建筑1，总共需要消耗1+200晶体矿和5+50高能瓦斯。
如果想要建造建筑4，需要先建造建筑1和建筑2，总共需要消耗1+10+66晶体矿和5+100+88高能瓦斯。 解题报告：
就是记忆化一个树形dp就行了呗，，不算难想。但是因为输入的巧妙，这题可以用巧妙的解法，详见下面Qls的思路。OrzOrz
AC代码：
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<map>
#include<vector>
#include<set>
#include<string>
#include<cmath>
#include<cstring>
#define ll long long
#define pb push_back
#define pm make_pair
#define fi first
#define se second
using namespace std;
const int MAX = 2e4 + 5;
struct Node {
int j,g;
} node[MAX];
int pre[MAX];
ll dpg[MAX],dpj[MAX];
ll dfsg(int cur,int root) {
if(cur == 1) return dpg[1] = node[1].g ;
if(dpg[cur] != -1) return dpg[cur];
dpg[cur]=0;
dpg[cur] += dfsg(pre[cur],cur);
dpg[cur] += node[cur].g;
return dpg[cur];
}
ll dfsj(int cur,int root) {
if(cur == 1) return dpj[1] = node[1].j ;
if(dpj[cur] != -1) return dpj[cur];
dpj[cur]=0;
dpj[cur] += dfsj(pre[cur],cur);
dpj[cur] += node[cur].j;
return dpj[cur];
}
int main()
{
int t,a,b,q,n;
cin>>t;
while(t--) {
memset(dpj,-1,sizeof dpj);
memset(dpg,-1,sizeof dpg);
//chushihua
scanf("%d%d",&n,&q);
for(int i = 1; i<=n; i++) {
scanf("%d%d",&node[i].j,&node[i].g);
}
for(int i = 2,x; i<=n; i++) {
scanf("%d",&x);
pre[i]=x;
}
for(int i = 1; i<=n; i++) {
dfsg(i,-1);
dfsj(i,-1);
}
int x;
while(q--) {
scanf("%d",&x);
printf("%lld %lld\n",dpj[x],dpg[x]);
}
}
return 0 ;
}
其实这个代码完全可以返回一个结构体或者用pair或者用两个引用，，但是这里因为懒惰，，没有改代码，（因为第一次写的时候不知道要求输出 晶体矿和高能瓦斯 分开输出。所以就写了一个dp，，然后发现输出格式后又懒得改然后就直接复制一波，改改变量就交了、）
Qls思路：（因为这题是按照顺序读入的：fi(1≤fi＜i) 所以可以这么写，，也算是个小技巧吧，，，不这么读入的话，就不能这么状态转移了，，所以还是老老实实写树上的吧）
#include<bits/stdc++.h>
using namespace std;
const int MAXN=20005;
int a[MAXN],b[MAXN];
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
int n,q;
scanf("%d%d",&n,&q);
for(int i=1;i<=n;i++)
scanf("%d%d",&a[i],&b[i]);
for(int i=2;i<=n;i++)
{
int f;
scanf("%d",&f);
a[i]+=a[f],b[i]+=b[f];
}
for(int i=1;i<=q;i++)
{
int x;
scanf("%d",&x);
printf("%d %d\n",a[x],b[x]);
}
}
return 0;
} ps：神仙就是神仙，，，一小时秒了九个题，，强势Rank1、、OrzOrz
京公网安备 11010502036488号