codeforces1110F Nearest Leaf

题面

题意

给出一棵树，它的节点的标号恰好为其dfs序，多次询问，每次询问给出三个数u,l,r，求点u到标号在 [ l , r ] [l,r] [l,r]中的叶子节点的最近距离。

做法

考虑用线段树维护点1到各个叶子节点的距离，发现若要维护点1的儿子节点点2到各个叶子节点的距离，只要将点2的子树中的所有叶子节点的距离减去边权，其余叶子节点加上边权，这样只要将询问离线，再维护区间加和区间最小值即可。

代码

#include<bits/stdc++.h>
#define ll long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N 500100
using namespace std;

ll n,Q,cl,tt,qq,lea[N],id[N],deep[N],in[N],out[N],ans[N];
bool il[N];
struct Node
{
	ll ls,rs,mn,sum;
}node[N<<1];
struct Que
{
	ll pos,l,r,id;
	bool operator < (const Que &u) const
	{
		return pos<u.pos;
	}
}que[N];
vector<ll>to[N],quan[N];

inline void ad(ll u,ll v,ll w)
{
	to[u].push_back(v);
	quan[u].push_back(w);
}

inline void up(ll now)
{
	ll L=node[now].ls,R=node[now].rs;
	node[now].mn=min(node[L].mn,node[R].mn)+node[now].sum;
}

void build(ll now,ll l,ll r)
{
	if(l==r)
	{
		node[now].mn=deep[lea[l]];
		return;
	}
	ll mid=((l+r)>>1);
	node[now].ls=++tt;
	build(tt,l,mid);
	node[now].rs=++tt;
	build(tt,mid+1,r);
	up(now);
}

void add(ll now,ll l,ll r,ll u,ll v,ll w)
{
	if(u<=l&&r<=v)
	{
		node[now].sum+=w;
		node[now].mn+=w;
		return;
	}
	ll mid=((l+r)>>1);
	if(u<=mid) add(node[now].ls,l,mid,u,v,w);
	if(v>mid) add(node[now].rs,mid+1,r,u,v,w);
	up(now);
}

ll ask(ll now,ll l,ll r,ll u,ll v)
{
	if(u<=l&&r<=v) return node[now].mn;
	ll res=INF,mid=((l+r)>>1);
	if(u<=mid) res=min(res,ask(node[now].ls,l,mid,u,v));
	if(mid<v) res=min(res,ask(node[now].rs,mid+1,r,u,v));
	return res+node[now].sum;
}

void dfs(ll now,ll last)
{
	ll i,q;
	bool flag=0;
	in[now]=cl+1;
	for(i=0;i<to[now].size();i++)
	{
		q=to[now][i];
		if(q==last) continue;
		flag=1;
		deep[q]=deep[now]+quan[now][i];
		dfs(q,now);
	}
	if(!flag) lea[++cl]=now,id[now]=cl,il[now]=1;
	out[now]=cl;
}

void Dfs(ll now,ll last)
{
	ll i,q;
	for(;qq<=Q&&que[qq].pos==now;qq++)
	{
		ans[que[qq].id]=ask(1,1,cl,in[que[qq].l],in[que[qq].r]-(!il[que[qq].r]));
	}
	for(i=0;i<to[now].size();i++)
	{
		q=to[now][i];
		if(q==last) continue;
		add(1,1,cl,in[q],out[q],-quan[now][i]);
		if(in[q]>1) add(1,1,cl,1,in[q]-1,quan[now][i]);//cerr<<1<<' '<<in[q]-1<<"+"<<endl;
		if(out[q]<cl) add(1,1,cl,out[q]+1,cl,quan[now][i]);//cerr<<out[q]+1<<" "<<cl<<"+"<<endl;
		Dfs(q,now);
		add(1,1,cl,in[q],out[q],quan[now][i]);
		if(in[q]>1) add(1,1,cl,1,in[q]-1,-quan[now][i]);
		if(out[q]<cl) add(1,1,cl,out[q]+1,cl,-quan[now][i]);
	}
}

int main()
{
	ll i,j,p,q;
	cin>>n>>Q;
	for(i=2;i<=n;i++)
	{
		scanf("%lld%lld",&p,&q);
		ad(i,p,q),ad(p,i,q);
	}
	for(i=1;i<=Q;i++)
	{
		scanf("%lld%lld%lld",&que[i].pos,&que[i].l,&que[i].r);
		que[i].id=i;
	}
	sort(que+1,que+Q+1);
	dfs(1,-1);
	build(tt=1,1,cl);
	qq=1;
	Dfs(1,-1);
	for(i=1;i<=Q;i++) printf("%lld\n",ans[i]);
}