【题解】【树链剖分+并查集+二分】
【线段树维护边的信息,类似next数组的存储。并查集维护父子信息和每个区间的起点终点。考虑每次限定一个速度范围,速度在这个范围内的边都可以操作。分治,每次做完一个区间再把当前不符合的递归到下一区间处理,由于存在回溯和分治两侧,所以这里并查集不能进行路径压缩。同时,按时间记录下修改操作】
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; struct tree{ int x,y,t; }que[140010]; int a[140010],nxt[140010],p[70010],tot; int f[70010],son[70010],dep[70010],size[70010],top[70010]; int fa[70010],s[70010],t[70010]; int go[1400010],to[1400010],link[1400010],point[262150],tt; int n,m,cur,ans[70010]; inline void add(int x,int y) { tot++; a[tot]=y; nxt[tot]=p[x]; p[x]=tot; tot++; a[tot]=x; nxt[tot]=p[y]; p[y]=tot; } int find(int x) { if(fa[x]==x) return x; fa[x]=find(fa[x]); } void dfs(int x,int F,int h) { size[x]=1; f[x]=F; dep[x]=h; for(int i=p[x];i!=-1;i=nxt[i]) if(a[i]!=F) { dfs(a[i],x,h+1); size[x]+=size[a[i]]; if(son[x]==-1||size[son[x]]<size[a[i]]) son[x]=a[i]; } } void DFS(int x,int tp) { top[x]=tp; if(son[x]==-1) return; DFS(son[x],tp); for(int i=p[x];i!=-1;i=nxt[i]) if(a[i]!=f[x]&&a[i]!=son[x]) DFS(a[i],a[i]); } inline int lca(int x,int y) { while(top[x]!=top[y]) if(dep[top[x]]<dep[top[y]]) swap(x,y); if(dep[x]<dep[y]) return x; return y; } inline int dis(int x,int y) { return dep[x]+dep[y]-2*dep[lca(x,y)]; } inline void solve(int x,int y,int &sum) { int l1,l2,s1=-1,tmp; x=find(x); y=find(y); tmp=dis(S[x],T[x]); if(tmp>s1) s1=tmp,l1=S[x],l2=T[x]; tmp=dis(S[x],S[y]); if(tmp>s1) s1=tmp,l1=S[x],l2=S[y]; tmp=dis(S[x],T[y]); if(tmp>s1) s1=tmp,l1=S[x],l2=T[y]; tmp=dis(T[x],S[y]); if(tmp>s1) s1=tmp,l1=T[x],l2=S[y]; tmp=dis(T[x],T[y]); if(tmp>s1) s1=tmp,l1=T[x],l2=T[y]; if(sum<s1) sum=s1; que[++cur].t=1,que[cur].x=y,que[cur].y=0; que[++cur].t=2,que[cur].x=x,que[cur].y=S[x]; que[++cur].t=3,que[cur].x=x,que[cur].y=T[x]; fa[y]=x; S[x]=l1; T[y]=l2; } inline void pushdown(int now) { while(cur>now) { if(!que[cur].t) dep[que[cur].x]--; if(que[cur].t==1) fa[que[cur].x]=que[cur].x; if(que[cur].t==2) S[que[cur].x]=que[cur].y; if(que[cur].t==3) T[que[cur].x]=que[cur].y; cur--; } } void build(int now,int l,int r,int al,int ar,int S,int T) { if(al<=l&&r<=ar) { tt++; go[tt]=S,to[tt]=T; link[tt]=point[S]; point[S]=tt; return; } int mid=(l+r)>>1; build((now<<1),l,mid,al,ar,S,T); build((now<<1)|1,mid+1,r,al,ar,S,T); } void ask(int now,int l,int r,int sum) { int pos=cur; for(int i=point[now];i!=-1;i=link[i]) solve(S[i],T[i],sum); if(l==r) { ans[l]=sum; pushdown(pos); return; } int mid=(l+r)>>1; ask((now<<1),l,mid,sum); ask((now<<1)|1,mid+1,r,sum); pushdown(pos); } int main() { int i; memset(p,-1,sizeof(p)); memset(nxt,-1,sizeof(nxt)); memset(son,-1,sizeof(son)); memset(link,-1,sizeof(link)); memset(point,-1,sizeof(point)); scanf("%d%d",&n,&m); for(i=1;i<n;++i) { int x,y,al,ar; scanf("%d%d%d%d",&x,&y,&al,&ar); add(x,y); build(1,1,n,al,ar,x,y); } dfs(1,0,1); DFS(1,1); for(i=1;i<=n;++i) fa[i]=s[i]=t[i]=i; ask(1,1,n,0); for(int i=1;i<=m;++i) { int x; scanf("%d",&x); printf("%d\n",ans[x]); } return 0; }