【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;
}