T2

【问题描述】
小 Z 有一棵 n 个节点的树，以 1 号节点为根，每条边有对应的权值，小
Z 经过时会收到对应权值的保护费。
现在有 q 个询问，每次询问如下：
若小 z 站在 x 号节点上，他需要凑齐至少 k 的路费才能回家，但小 z 每
次只能往下走 (也就是只能往子树方向走)，小 z 想知道凑齐路费的最小步数
是多少 (若无法凑齐路费则输出 −1)。经过每条边花费的步数为 1 步。
【输入格式】
从文件 b.in 中读入数据.
第一行一个正整数 id(1 ≤ id ≤ 20) 表示该数据是第 id 号测试点，这将
有助于你取得部分分。
第二行一个正整数 n(n ≥ 2)。
接下来 n−1 行每行三个正整数 u, v, w，代表 u 和 v 节点之间有一条权
值为 w 的边。
接下来一行一个正整数 q。
最后 q 行每行两个正整数 x, k，意义如题。
【输出格式】
输出到文件 b.out 中.
对于每个询问输出一个整数表示答案，若无法凑齐路费则输出 −1。
【样例输入 1】
1
9
1 2 2
2 3 2
3 4 6
4
3 8 4
2 5 5
5 6 2
2 7 6
1 9 3
4
2 5
3 8
1 7
1 10
【样例输出 1】
1
-1
2
3

代码放上，自行体会：

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+10;
struct node{
	int val,lc,rc;
}tr[maxn*20];
int n,Q;
inline int read(){
	int x=0,f=1;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
	while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+c-'0';c=getchar();}
	return x*f;
}
int beg[maxn],nex[maxn<<1],to[maxn<<1],w[maxn<<1],e;
inline void add(int x,int y,int z){
	e++;nex[e]=beg[x];beg[x]=e;
	to[e]=y;w[e]=z;
}
int dis[maxn],dep[maxn];
inline void dfs(int x,int fa){
	dep[x]=dep[fa]+1;
	for(int i=beg[x];i;i=nex[i]){
		int t=to[i];
		if(t==fa)continue;
		dis[t]=dis[x]+w[i];
		dfs(t,x);
	}
}
vector<pair<int,int> >q[maxn];
int ans[maxn];
int rt[maxn],cnt,Max;
inline int update(int h,int l,int r,int x,int y){
	if(!h)h=++cnt;
	tr[h].val=max(tr[h].val,y);
	if(l==r)return h;
	int mid=(l+r)>>1;
	if(mid>=x)tr[h].lc=update(tr[h].lc,l,mid,x,y);
	else tr[h].rc=update(tr[h].rc,mid+1,r,x,y);
	return h;
}
inline int merge(int a,int b,int l,int r){
	if(!a)return b;
	if(!b)return a;
	tr[a].val=max(tr[a].val,tr[b].val);
	if(l==r)return a;
	int mid=(l+r)>>1;
	tr[a].lc=merge(tr[a].lc,tr[b].lc,l,mid);
	tr[a].rc=merge(tr[a].rc,tr[b].rc,mid+1,r);
	return a;
}
inline int query(int h,int l,int r,int x){
	if(l==r)return l;
	int mid=(l+r)>>1;
	if(tr[tr[h].lc].val>=x)return query(tr[h].lc,l,mid,x);
	else return query(tr[h].rc,mid+1,r,x); 
}
inline void solve(int x,int fa){
	rt[x]=update(rt[x],1,Max,dep[x],dis[x]);
	for(int i=beg[x];i;i=nex[i]){
		int t=to[i];
		if(t==fa)continue;
		solve(t,x);
		rt[x]=merge(rt[x],rt[t],1,Max);
	}
	int a,b;
	for(int i=0;i<q[x].size();i++){
		a=q[x][i].first+dis[x];b=q[x][i].second;
		if(tr[rt[x]].val<a)ans[b]=-1;
		else ans[b]=query(rt[x],1,Max,a)-dep[x];
	}
}
int main(){
	freopen("b.in","r",stdin);
	freopen("b.out","w",stdout);
	read(),n=read();
	int x,y,z;
	for(int i=1;i<n;i++){
		x=read(),y=read(),z=read();
		add(x,y,z),add(y,x,z);
	}
	dfs(1,0);
	for(int i=1;i<=n;i++)
		Max=max(Max,dep[i]);
	Q=read();
	for(int i=1;i<=Q;i++){
		x=read(),y=read();
		q[x].push_back(make_pair(y,i));
	}
	solve(1,0);
	for(int i=1;i<=Q;i++)
		printf("%d
",ans[i]);
	return 0;
}

深深地感到自己的弱小。