P14248 题解

#include <bits/stdc++.h>
#define int long long
#define mid ((l+r)>>1)
using namespace std;
int n,q;
vector<pair<int,int>> vc[500005];
int u[500005],v[500005],w[500005];
int siz[500005],rt,mv=1e9;
void getsiz(int now,int fa){
	int maxv=0; siz[now]=1;
	for(auto x:vc[now]){
		if(x.first==fa) continue;
		getsiz(x.first,now);
		siz[now]+=siz[x.first];
		maxv=max(maxv,siz[x.first]);
	}
	maxv=max(maxv,n-siz[now]);
	if(maxv<mv) mv=maxv,rt=now;
}
int ord[1000005],st[500005],cnt;
int dep[500005],ind[500005],outd[500005],invd[500005],tot;
void dfs0(int now,int fa){
	siz[now]=1;
	st[now]=++cnt; ord[cnt]=now;
	ind[now]=++tot,invd[tot]=now;
	for(auto x:vc[now]){
		if(x.first==fa) continue;
		dep[x.first]=dep[now]+x.second;
		dfs0(x.first,now);
		siz[now]+=siz[x.first];
		ord[++cnt]=now;
	}
	outd[now]=tot;
}
int minv[20][1000005],lg2[1000005];
int dist(int l,int r){
	int ans=dep[l]+dep[r];
	l=st[l],r=st[r];
	if(l>r) swap(l,r);
	int k=lg2[r-l+1];
	return ans-2*min(minv[k][l],minv[k][r-(1<<k)+1]);
}
int qa[500005],qb[500005],qk[500005],ans[500005];
vector<int> cg[500005],qy[500005];
pair<int,int> merge(pair<int,int> x,pair<int,int> y){
	if(x==make_pair(-1ll,-1ll)) return y;
	if(y==make_pair(-1ll,-1ll)) return x;
	int max1=dist(x.first,y.first);
	int max2=dist(x.first,y.second);
	int max3=dist(x.second,y.first);
	int max4=dist(x.second,y.second);
	int max5=dist(x.first,x.second);
	int max6=dist(y.first,y.second);
	int maxv=max({max1,max2,max3,max4,max5,max6});
	if(max1==maxv) return {x.first,y.first};
	if(max2==maxv) return {x.first,y.second};
	if(max3==maxv) return {x.second,y.first};
	if(max4==maxv) return {x.second,y.second};
	if(max5==maxv) return {x.first,x.second};
	if(max6==maxv) return {y.first,y.second};
}
struct sgt{
	pair<int,int> f[2000005];
	void build(int i,int l,int r){
		f[i]={-1,-1};
		if(l==r) return ;
		build(i<<1,l,mid),build(i<<1|1,mid+1,r);
	}
	void change(int i,int l,int r,int pos){
		if(l==r){
			f[i]={invd[l],invd[l]};
			return ;
		}
		if(pos<=mid) change(i<<1,l,mid,pos);
		else change(i<<1|1,mid+1,r,pos);
		f[i]=merge(f[i<<1],f[i<<1|1]);
	}
	pair<int,int> qry(int i,int l,int r,int ql,int qr){
		if(ql>qr) return {-1ll,-1ll};
		if(ql<=l&&r<=qr) return f[i];
		if(qr<=mid) return qry(i<<1,l,mid,ql,qr);
		if(ql>mid) return qry(i<<1|1,mid+1,r,ql,qr);
		return merge(qry(i<<1,l,mid,ql,qr),qry(i<<1|1,mid+1,r,ql,qr));
	}
}tree;
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	for(int i=2;i<=1000000;i++) lg2[i]=lg2[i>>1]+1;
	cin>>n>>q;
	for(int i=1;i<n;i++){
		cin>>u[i]>>v[i]>>w[i];
		vc[u[i]].push_back({v[i],w[i]});
		vc[v[i]].push_back({u[i],w[i]});
	}
	getsiz(1,0);
	dfs0(rt,0);
	for(int i=1;i<n;i++) if(dep[u[i]]>dep[v[i]]) swap(u[i],v[i]);
	for(int i=1;i<=cnt;i++) minv[0][i]=dep[ord[i]];
	for(int j=1;j<=19;j++) for(int i=1;i+(1<<j)-1<=cnt;i++) minv[j][i]=min(minv[j-1][i],minv[j-1][i+(1<<(j-1))]);
	for(int i=1;i<=n;i++) cg[siz[i]].push_back(i);
	for(int i=1;i<=q;i++) cin>>qa[i]>>qb[i]>>qk[i],qy[qk[i]].push_back(i);
	tree.build(1,1,n);
	for(int i=n;i>=1;i--){
		for(auto x:cg[i]) tree.change(1,1,n,ind[x]);
		for(auto x:qy[i]){
			int maxv=0;
			pair<int,int> p1=tree.qry(1,1,n,ind[v[qa[x]]],outd[v[qa[x]]]);
			pair<int,int> p2=merge(tree.qry(1,1,n,1,ind[v[qa[x]]]-1),tree.qry(1,1,n,outd[v[qa[x]]]+1,n));
			if(p1!=make_pair(-1ll,-1ll)) maxv=max(maxv,dist(p1.first,p1.second));
			if(p2!=make_pair(-1ll,-1ll)) maxv=max(maxv,dist(p2.first,p2.second));
			if(p1!=make_pair(-1ll,-1ll)&&p2!=make_pair(-1ll,-1ll)){
				int d1=max(dist(p1.first,v[qa[x]]),dist(p1.second,v[qa[x]]));
				int d2=max(dist(p2.first,u[qa[x]]),dist(p2.second,u[qa[x]]));
				maxv=max(maxv,d1+d2+qb[x]);
			}
			ans[x]=maxv;
		}
	}
	for(int i=1;i<=q;i++) cout<<ans[i]<<"\n";
	return 0;
}