广州站是指哪个站,宁波个人网站建设,南宁网页搭建软件,wordpress大学 主题题干#xff1a;
在星际争霸(StarCraft)中#xff0c;有3个种族。对于任意一个种族#xff0c;他们的建筑建造都是有一个顺序的。这个顺序正好是一个树形结构#xff0c;我们称之为科技树(Technology tree)。
在科技树中#xff0c;只有一个建筑是不需要前…题干
在星际争霸(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组数据。对于每组数据
第一行包含两个正整数nq(1≤n,q≤20000)表示有n个建筑和q次查询。
接下来n行每行包含两个整数a,b(0≤a,b≤300)表示建造建筑i需要花费a晶体矿和b高能瓦斯。
接下来一行包含n-1个正整数f(1≤f≤n)。第i个(1≤in)正整数fi(1≤fii)表示建筑i1的前置建筑为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总共需要消耗110晶体矿和5100高能瓦斯。
如果想要建造建筑3需要先建造建筑1总共需要消耗1200晶体矿和550高能瓦斯。
如果想要建造建筑4需要先建造建筑1和建筑2总共需要消耗11066晶体矿和510088高能瓦斯。
解题报告 就是记忆化一个树形dp就行了呗不算难想。但是因为输入的巧妙这题可以用巧妙的解法详见下面Qls的思路。OrzOrz AC代码
#includecstdio
#includeiostream
#includealgorithm
#includequeue
#includemap
#includevector
#includeset
#includestring
#includecmath
#includecstring
#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;cint;while(t--) {memset(dpj,-1,sizeof dpj);memset(dpg,-1,sizeof dpg); //chushihuascanf(%d%d,n,q);for(int i 1; in; i) {scanf(%d%d,node[i].j,node[i].g);}for(int i 2,x; in; i) {scanf(%d,x);pre[i]x;}for(int i 1; in; 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≤fii) 所以可以这么写也算是个小技巧吧不这么读入的话就不能这么状态转移了所以还是老老实实写树上的吧
#includebits/stdc.h
using namespace std;
const int MAXN20005;
int a[MAXN],b[MAXN];
int main()
{int T;scanf(%d,T);while(T--){int n,q;scanf(%d%d,n,q);for(int i1;in;i)scanf(%d%d,a[i],b[i]);for(int i2;in;i){int f;scanf(%d,f);a[i]a[f],b[i]b[f];}for(int i1;iq;i){int x;scanf(%d,x);printf(%d %d\n,a[x],b[x]);}}return 0;
}
ps神仙就是神仙一小时秒了九个题强势Rank1、、OrzOrz