LYDSY模拟赛day2 Dash Speed

LYDSY模拟赛day2 Dash Speed

LYDSY模拟赛day2 Dash Speed

/*
弃坑
*/
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=,M=N*;
int n,m,i,g[N],v[N<<],nxt[N<<],ed,cur,ans[N];
int size[N],f[N],d[N],son[N],top[N];
int fa[N],dep[N],A[N],B[N];
int G[],V[M],W[M],NXT[M],ED;
struct E{int t,x,y;E(){}E(int _t,int _x,int _y){t=_t,x=_x,y=_y;}}q[N<<];
void add(int x,int y){v[++ed]=y;nxt[ed]=g[x];g[x]=ed;}
void dfs(int x){
size[x]=;
for(int i=g[x];i;i=nxt[i])if(v[i]!=f[x]){
f[v[i]]=x,d[v[i]]=d[x]+;
dfs(v[i]),size[x]+=size[v[i]];
if(size[v[i]]>size[son[x]])son[x]=v[i];
}
}
void dfs2(int x,int y){
top[x]=y;
if(son[x])dfs2(son[x],y);
for(int i=g[x];i;i=nxt[i])if(v[i]!=son[x]&&v[i]!=f[x])dfs2(v[i],v[i]);
}
int lca(int x,int y){
for(;top[x]!=top[y];x=f[top[x]])if(d[top[x]]<d[top[y]])swap(x,y);
return d[x]<d[y]?x:y;
}
int dis(int x,int y){return d[x]+d[y]-*d[lca(x,y)];}
int F(int x){return fa[x]==x?x:F(fa[x]);}
void merge(int x,int y,int&ret){
x=F(x),y=F(y);
int u,v,t=-,tmp;
tmp=dis(A[x],B[x]);
if(tmp>t)t=tmp,u=A[x],v=B[x];
tmp=dis(A[x],A[y]);
if(tmp>t)t=tmp,u=A[x],v=A[y];
tmp=dis(A[x],B[y]);
if(tmp>t)t=tmp,u=A[x],v=B[y];
tmp=dis(B[x],A[y]);
if(tmp>t)t=tmp,u=B[x],v=A[y];
tmp=dis(B[x],B[y]);
if(tmp>t)t=tmp,u=B[x],v=B[y];
tmp=dis(A[y],B[y]);
if(tmp>t)t=tmp,u=A[y],v=B[y];
if(ret<t)ret=t;
if(dep[x]==dep[y]){
dep[x]++;
q[++cur]=E(,x,);
}
if(dep[x]<dep[y])swap(x,y);
q[++cur]=E(,y,);
q[++cur]=E(,x,A[x]);
q[++cur]=E(,x,B[x]);
fa[y]=x,A[x]=u,B[x]=v;
}
void retrace(int t){
while(cur>t){
if(!q[cur].t)dep[q[cur].x]--;
if(q[cur].t==)fa[q[cur].x]=q[cur].x;
if(q[cur].t==)A[q[cur].x]=q[cur].y;
if(q[cur].t==)B[q[cur].x]=q[cur].y;
cur--;
}
}
void ins(int x,int a,int b,int c,int d,int p,int q){
if(c<=a&&b<=d){
V[++ED]=p;
W[ED]=q;
NXT[ED]=G[x];
G[x]=ED;
return;
}
int mid=(a+b)>>;
if(c<=mid)ins(x<<,a,mid,c,d,p,q);
if(d>mid)ins(x<<|,mid+,b,c,d,p,q);
}
void solve(int x,int a,int b,int ret){
int pos=cur;
for(int i=G[x];i;i=NXT[i])merge(V[i],W[i],ret);
if(a==b){
ans[a]=ret;
retrace(pos);
return;
}
int mid=(a+b)>>;
solve(x<<,a,mid,ret);
solve(x<<|,mid+,b,ret);
retrace(pos);
}
int main(){
freopen("speed.in","r",stdin);freopen("speed.out","w",stdout);
scanf("%d%d",&n,&m);
for(i=;i<n;i++){
int x,y,l,r;
scanf("%d%d%d%d",&x,&y,&l,&r);
add(x,y),add(y,x);
ins(,,n,l,r,x,y);
}
dfs();dfs2(,);
for(i=;i<=n;i++)fa[i]=A[i]=B[i]=i;
solve(,,n,);
while(m--)scanf("%d",&i),printf("%d\n",ans[i]);
fclose(stdin);fclose(stdout);
return ;
}
上一篇:LYDSY模拟赛day2 Divisors


下一篇:【洛谷】NOIP提高组模拟赛Day2【动态开节点/树状数组】【双头链表模拟】