「2017 山东三轮集训 Day7 解题报告

「2017 山东三轮集训 Day7」Easy

练习一下动态点分

每个点开一个线段树维护子树到它的距离

然后随便查询一下就可以了

注意线段树开大点...

---

Code:

#include <cstdio>

#include <cctype>

#include <algorithm>

using std::min;

template <class T>

void read(T &x)

{

	x=0;char c=getchar();

	while(!isdigit(c)) c=getchar();

	while(isdigit(c)) x=x*10+c-'0',c=getchar();

}

const int N=1e5+10;

const int inf=0x3f3f3f3f;

int head[N],to[N<<1],Next[N<<1],edge[N<<1],cnt;

void add(int u,int v,int w)

{

	to[++cnt]=v,edge[cnt]=w,Next[cnt]=head[u],head[u]=cnt;

}

namespace RMQLCA

{

	int st[19][N<<1],Log[N<<1],dfn[N],dep[N],dis[N],clock;

	void dfs(int now,int fa)

	{

		dep[now]=dep[fa]+1;

		st[0][++clock]=now;

		dfn[now]=clock;

		for(int v,i=head[now];i;i=Next[i])

			if((v=to[i])!=fa)

				dis[v]=dis[now]+edge[i],dfs(v,now),st[0][++clock]=now;

	}

	void init()

	{

		dfs(1,0);

		for(int i=2;i<=clock;i++) Log[i]=Log[i>>1]+1;

		for(int j=1;j<=18;j++)

			for(int i=1;i<=clock-(1<<j)+1;i++)

			{

				int x=st[j-1][i],y=st[j-1][i+(1<<j-1)];

				st[j][i]=dep[x]<dep[y]?x:y;

			}

	}

	int LCA(int x,int y)

	{

		x=dfn[x],y=dfn[y];

		if(x>y) std::swap(x,y);

		int d=Log[y+1-x];

		x=st[d][x],y=st[d][y-(1<<d)+1];

		return dep[x]<dep[y]?x:y;

	}

	int getdis(int x,int y)

	{

		return dis[x]+dis[y]-(dis[LCA(x,y)]<<1);

	}

}

namespace seg

{

    #define ls ch[now][0]

    #define rs ch[now][1]

	int ch[N*100][2],mi[N*100],tot;

	void ins(int &now,int l,int r,int p,int d)

	{

		if(!now) now=++tot;

		if(l==r) {mi[now]=d;return;}

		int mid=l+r>>1;

		if(p<=mid) ins(ls,l,mid,p,d);

		else ins(rs,mid+1,r,p,d);

		mi[now]=min(mi[ls],mi[rs]);

	}

	int query(int now,int L,int R,int l,int r)

	{

		if(!now) return inf;

		if(L==l&&R==r) return mi[now];

		int Mid=L+R>>1;

		if(r<=Mid) return query(ls,L,Mid,l,r);

		else if(l>Mid) return query(rs,Mid+1,R,l,r);

		else return min(query(ls,L,Mid,l,Mid),query(rs,Mid+1,R,Mid+1,r));

	}

	void init()

	{

		mi[0]=inf;

	}

}

using RMQLCA::getdis;

using seg::query;

using seg::ins;

int siz[N],del[N],par[N],root[N],si,mi,rt,n,m;

void dfsrt(int now,int fa)

{

	siz[now]=1;

	int mx=0;

	for(int v,i=head[now];i;i=Next[i])

		if((v=to[i])!=fa&&!del[v])

		{

			dfsrt(v,now);

			siz[now]+=siz[v];

			mx=mx>siz[v]?mx:siz[v];

		}

	mx=mx>si-siz[now]?mx:si-siz[now];

	if(mx<mi) mi=mx,rt=now;

}

void dfs(int now,int rt,int fa,int dis)

{

	ins(root[rt],1,n,now,dis);

	siz[now]=1;

	for(int v,i=head[now];i;i=Next[i])

		if((v=to[i])!=fa&&!del[v])

			dfs(v,rt,now,dis+edge[i]),siz[now]+=siz[v];

}

void divide(int now)

{

	del[now]=1;

	dfs(now,now,0,0);

	for(int v,i=head[now];i;i=Next[i])

		if(!del[v=to[i]])

		{

			si=siz[v],mi=n;

			dfsrt(v,0);

			par[rt]=now;

			divide(rt);

		}

}

int main()

{

	read(n);

	for(int u,v,d,i=1;i<n;i++) read(u),read(v),read(d),add(u,v,d),add(v,u,d);

	RMQLCA::init();

	seg::init();

	si=n,mi=n,dfsrt(1,0),divide(rt);

	read(m);

	for(int l,r,x,s,ans,i=1;i<=m;i++)

	{

		read(l),read(r),read(x),s=x;

		ans=inf;

		while(x)

		{

			int mi=query(root[x],1,n,l,r);

			ans=min(ans,mi+getdis(s,x));

			x=par[x];

		}

		printf("%d\n",ans);

	}

	return 0;

}

---

2019.3.17