【NowCoder368E】车站（线段树）

时间：2023-12-14 18:36:56

【NowCoder368E】车站（线段树）

题面

牛客网

题解

链交的结果显然和求解的顺序无关，因此我们可以拿线段树维护区间链的链交结果。

然后怎么求解最远点。

维护链交的时候再记录两个点表示到达链交两个端点的最远点编号，合并的时候也维护一下。

这样子就可以啦。

然后分类讨论论论论论论论论一下就好了。

#include<iostream>

#include<cstdio>

using namespace std;

#define MAX 100100

#define lson (now<<1)

#define rson (now<<1|1)

inline int read()

{

	int x=0;bool t=false;char ch=getchar();

	while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();

	if(ch=='-')t=true,ch=getchar();

	while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();

	return t?-x:x;

}

struct Line{int v,next;}e[MAX<<1];

int h[MAX],cnt=1;

inline void Add(int u,int v){e[cnt]=(Line){v,h[u]};h[u]=cnt++;}

int st[20][MAX<<1],lg[MAX<<1],sum,p[20][MAX];

int n,m,Q,dep[MAX],dfn[MAX],low[MAX];

void dfs(int u,int ff)

{

	st[0][dfn[u]=++sum]=u;dep[u]=dep[ff]+1;p[0][u]=ff;

	for(int i=h[u];i;i=e[i].next)

		if(e[i].v!=ff)

			dfs(e[i].v,u),st[0][++sum]=u;

	low[u]=sum;

}

int Chk1(int a,int b){return dep[a]<dep[b]?a:b;}

int Chk2(int a,int b){return dep[a]>dep[b]?a:b;}

int LCA(int u,int v)

{

	u=dfn[u],v=dfn[v];if(u>v)swap(u,v);

	int l=lg[v-u+1];

	return Chk1(st[l][u],st[l][v-(1<<l)+1]);

}

int Kth(int x,int K)

{

	for(int i=lg[n];~i;--i)

		if(K&(1<<i))x=p[i][x];

	return x;

}

int Dis(int u,int v){return dep[u]+dep[v]-2*dep[LCA(u,v)];}

struct Data{int x,y,z,sx,sy;}t[MAX<<2];

Data Make(int x,int y){return (Data){x,y,LCA(x,y),x,y};}

Data operator+(Data a,Data b)

{

	Data c;c.x=-1;if(a.x==-1||b.x==-1)return c;

	if(dep[a.z]<dep[b.z])swap(a,b);

	if(LCA(a.z,b.x)!=a.z&&LCA(a.z,b.y)!=a.z)return c;

	c.x=Chk2(LCA(a.x,b.x),LCA(a.x,b.y));

	c.y=Chk2(LCA(a.y,b.x),LCA(a.y,b.y));

	if(Dis(a.sx,c.x)>Dis(a.sx,c.y))swap(a.sx,a.sy);

	if(Dis(b.sx,c.x)>Dis(b.sx,c.y))swap(b.sx,b.sy);

	c.sx=(Dis(c.x,a.sx)<Dis(c.x,b.sx))?b.sx:a.sx;

	c.sy=(Dis(c.y,a.sy)<Dis(c.y,b.sy))?b.sy:a.sy;

	c.z=LCA(c.x,c.y);return c;

}

void Build(int now,int l,int r)

{

	if(l==r){int x=read(),y=read();t[now]=Make(x,y);return;}

	int mid=(l+r)>>1;

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

	t[now]=t[lson]+t[rson];

}

void Modify(int now,int l,int r,int p)

{

	if(l==r){int x=read(),y=read();t[now]=Make(x,y);return;}

	int mid=(l+r)>>1;

	if(p<=mid)Modify(lson,l,mid,p);

	else Modify(rson,mid+1,r,p);

	t[now]=t[lson]+t[rson];

}

Data Query(int now,int l,int r,int L,int R)

{

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

	int mid=(l+r)>>1;

	if(R<=mid)return Query(lson,l,mid,L,R);

	if(L>mid)return Query(rson,mid+1,r,L,R);

	return Query(lson,l,mid,L,mid)+Query(rson,mid+1,r,mid+1,R);

}

int Calc(Data a)

{

	if(a.x==-1)return -1;

	int D=Dis(a.sx,a.sy),d=Dis(a.x,a.y),dx=Dis(a.x,a.sx),dy=Dis(a.y,a.sy);

	if(dx>dy)swap(dx,dy),swap(a.x,a.y),swap(a.sx,a.sy);

	if(dy>=dx+d)return a.y;

	int l,r;

	l=D/2-dx,r=(D+1)/2-dy;

	int A=(dep[a.x]-dep[a.z]>=l)?Kth(a.x,l):Kth(a.y,r);

	l=(D+1)/2-dx,r=D/2-dy;

	int B=(dep[a.x]-dep[a.z]>=l)?Kth(a.x,l):Kth(a.y,r);

	return min(A,B);

}

int main()

{

	n=read();m=read();

	for(int i=2;i<=n+n;++i)lg[i]=lg[i>>1]+1;

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

	dfs(1,0);

	for(int j=1;j<=lg[sum];++j)

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

			st[j][i]=Chk1(st[j-1][i],st[j-1][i+(1<<(j-1))]);

	for(int j=1;j<=lg[sum];++j)

		for(int i=1;i<=n;++i)

			p[j][i]=p[j-1][p[j-1][i]];

	Build(1,1,m);

	Q=read();

	while(Q--)

	{

		int opt=read(),x=read();

		if(opt==1)printf("%d\n",Calc(Query(1,1,m,x,read())));

		else Modify(1,1,m,x);

	}

	return 0;

}

相关文章