Problem:
比特山是比特镇的飙车圣地。在比特山上一共有 (n) 个广场，编号依次为 (1) 到 (n)，这些广场之间通过
(n − 1) 条双向车道直接或间接地连接在一起，形成了一棵树的结构。
因为每条车道的修建时间以及建筑材料都不尽相同，所以可以用两个数字$ l_i, r_i $量化地表示一条车道
的承受区间，只有当汽车以不小于 (l_i) 且不大于 (r_i) 的速度经过这条车道时，才不会对路面造成伤害。
Byteasar 最近新买了一辆跑车，他想在比特山飙一次车。Byteasar 计划选择两个不同的点 (，S, T，)然
后在它们树上的最短路径上行驶，且不对上面任意一条车道造成伤害。
Byteasar 不喜欢改变速度，所以他会告诉你他的车速。为了挑选出最合适的车速，Byteasar 一共会
向你询问 (m) 次。请帮助他找到一条合法的道路，使得路径上经过的车道数尽可能多。
Input
第一行包含两个正整数(， n, m，)表示广场的总数和询问的总数。
接下来 n − 1 行，每行四个正整数 (，u_i, v_i, l_i, r_i，)表示一条连接 (u_i) 和 (v_i) 的双向车道，且承受区间为([l_i, r_i])。
接下来 m 行，每行一个正整数 (q_i)，分别表示每个询问的车速。
Output
输出 m 行，每行一个整数，其中第 (i) 行输出车速为 (i) 时的最长路径的长度，如果找不到合法的路
径则输出 0。
对于 100% 的数据，(1 ≤ u_i, v_i, q_i ≤ n, 1 ≤ l_i ≤ r_i ≤ n)。
线段树分治&&动态树&&可撤销并查集
预处理出所有车速时的答案，
在车速区间[1,n]进行递归
进入区间[l,r]时，将全部覆盖此速度区间的边加入。
离开时还原。
递归到叶子节点时计算答案。
答案是此时森林的最长链。
我们用并查集维护树的直径的两个端点，当合并两颗树时，答案只可能在这四个端点中产生,共6种情况，取最大值。
Code
const int N=70010,M=N*20;
int n,m,i,g[N],v[N<<1],nxt[N<<1],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[262150],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<<2];
void add(int x,int y){v[++ed]=y;nxt[ed]=g[x];g[x]=ed;}
void dfs(int x){
size[x]=1;
for(int i=g[x];i;i=nxt[i])if(v[i]!=f[x]){
f[v[i]]=x,d[v[i]]=d[x]+1;
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]-2*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=-1,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(0,x,0);
}
if(dep[x]<dep[y])swap(x,y);
q[++cur]=E(1,y,0);
q[++cur]=E(2,x,A[x]);
q[++cur]=E(3,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==1)fa[q[cur].x]=q[cur].x;
if(q[cur].t==2)A[q[cur].x]=q[cur].y;
if(q[cur].t==3)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)>>1;
if(c<=mid)ins(x<<1,a,mid,c,d,p,q);
if(d>mid)ins(x<<1|1,mid+1,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)>>1;
solve(x<<1,a,mid,ret);
solve(x<<1|1,mid+1,b,ret);
retrace(pos);
}
int main(){
scanf("%d%d",&n,&m);
for(i=1;i<n;i++){
int x,y,l,r;
scanf("%d%d%d%d",&x,&y,&l,&r);
add(x,y),add(y,x);
ins(1,1,n,l,r,x,y);
}
dfs(1);dfs2(1,1);
for(i=1;i<=n;i++)fa[i]=A[i]=B[i]=i;
solve(1,1,n,0);
while(m--)scanf("%d",&i),printf("%d
",ans[i]);
return 0;
}