【百度之星初赛A】路径交

Problem Description

给定一棵n个点的树，以及m条路径，每次询问第L条到第R条路径的交集部分的长度（如果一条边同时出现在2条路径上，那么它属于路径的交集）。

Input

第一行一个数n（n<=500,000）

接下来n-1行，每行三个数x，y，z，表示一条从x到y并且长度为z的边第n+1行一个数m（m<=500,000）

接下来m行，每行两个数u，v，表示一条从u到v的路径

接下来一行一个数Q，表示询问次数（Q<=500,000）

接下来Q行，每行两个数L和R

Output

Q行，每行一个数表示答案。

Sample Input

Sample Output

题解：看到题的第一反应就是线段树，然后在区间合并的时候求一下两个路径的交即可，现在我们只需要快速求出两个路径的交即可。

设两条路径分别为a1-b1,a2-b2，它们的lca是c1,c2，求出a1,b1-a2,b2两两之间的lca，设分别为d1,d2,d3,d4，假设dep[d1]<=dep[d2]<=dep[d3]<=dep[d4]，dep[c1]<=dep[c2]。那么如果两条路径有交，当且仅当dep[d1]>=dep[c1]且dep[d4]>=dep[d3]>=dep[c2]（自己画画就知道了）。并且如果有交，那么交一定是d3-d4。

如果用RMQ求LCA，则时间复杂度为nlogn。

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

#define lson x<<1

#define rson x<<1|1

using namespace std;

const int maxn=500010;

typedef long long ll;

struct path

{

	int a,b,c;

	path(){}

	path(int A,int B,int C)	{a=A,b=B,c=C;}

}p[maxn],s[maxn<<2];

int n,m,q,cnt;

int mn[20][maxn<<1],Log[maxn<<1],pos[maxn],dep[maxn],fa[maxn];

int head[maxn],nxt[maxn<<1],val[maxn<<1],to[maxn<<1];

int cs[10];

ll len[maxn];

int MN(int a,int b)

{

	return dep[a]<dep[b]?a:b;

}

int lca(int a,int b)

{

	int x=pos[a],y=pos[b];

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

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

	return MN(mn[k][x],mn[k][y-(1<<k)+1]);

}

bool cmp(int a,int b)

{

	return dep[a]<dep[b];

}

path mix(path x,path y)

{

	if(!x.c||!y.c)	return path(0,0,0);

	cs[1]=lca(x.a,y.a),cs[2]=lca(x.a,y.b),cs[3]=lca(x.b,y.a),cs[4]=lca(x.b,y.b);

	sort(cs+1,cs+5,cmp);

	int md=max(dep[x.c],dep[y.c]),nd=min(dep[x.c],dep[y.c]);

	if(dep[cs[1]]<nd||dep[cs[3]]<md)	return path(0,0,0);

	else	return path(cs[3],cs[4],lca(cs[3],cs[4]));

}

inline int rd()

{

	int ret=0,f=1;	char gc=getchar();

	while(gc<'0'||gc>'9')	{if(gc=='-')f=-f;	gc=getchar();}

	while(gc>='0'&&gc<='9')	ret=ret*10+gc-'0',gc=getchar();

	return ret*f;

}

void add(int a,int b,int c)

{

	to[cnt]=b,val[cnt]=c,nxt[cnt]=head[a],head[a]=cnt++;

}

void dfs(int x)

{

	pos[x]=++pos[0],mn[0][pos[0]]=x;

	for(int i=head[x];i!=-1;i=nxt[i])

	{

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

		{

			fa[to[i]]=x,dep[to[i]]=dep[x]+1,len[to[i]]=len[x]+val[i],dfs(to[i]);

			mn[0][++pos[0]]=x;

		}

	}

}

void build(int l,int r,int x)

{

	if(l==r)

	{

		s[x]=p[l];

		return ;

	}

	int mid=l+r>>1;

	build(l,mid,lson),build(mid+1,r,rson);

	s[x]=mix(s[lson],s[rson]);

}

path query(int l,int r,int x,int a,int b)

{

	if(a<=l&&r<=b)	return s[x];

	int mid=l+r>>1;

	if(b<=mid)	return query(l,mid,lson,a,b);

	if(a>mid)	return query(mid+1,r,rson,a,b);

	return mix(query(l,mid,lson,a,b),query(mid+1,r,rson,a,b));

}

int main()

{

	n=rd();

	int i,j,a,b,c;

	memset(head,-1,sizeof(head));

	for(i=1;i<n;i++)	a=rd(),b=rd(),c=rd(),add(a,b,c),add(b,a,c);

	dep[1]=1,dfs(1);

	for(i=2;i<=2*n-1;i++)	Log[i]=Log[i>>1]+1;

	for(j=1;(1<<j)<=2*n-1;j++)	for(i=1;i+(1<<j)-1<=2*n-1;i++)	mn[j][i]=MN(mn[j-1][i],mn[j-1][i+(1<<j-1)]);

	m=rd();

	for(i=1;i<=m;i++)	p[i].a=rd(),p[i].b=rd(),p[i].c=lca(p[i].a,p[i].b);

	build(1,m,1);

	q=rd();

	for(i=1;i<=q;i++)

	{

		a=rd(),b=rd();

		path ans=query(1,m,1,a,b);

		printf("%lld\n",len[ans.a]+len[ans.b]-2*len[ans.c]);

	}

	return 0;

}

巴特西

【百度之星初赛A】路径交 LCA+线段树