测试点1～2：暴力。
测试点3～4：可以将边按r从大到小排序不断加入，然后用并茶几维护深度。好像也可以用猫树做。
好吧其他的部分分并没有看懂。
正解：
线段树分治，求出每个速度的答案。
对于速度区间$[L,R]$，将完全包含这个区间的边加入，对于其余的边，按照和mid的关系分到左右儿子，这里的一条边有可能同时分到两个儿子所以直接塞vector就行了。
那么到达叶子区间时，满足条件的树的结构已经出来了，答案就是这些联通块的直径。
那么大体思路已经清晰了，如何动态维护树的结构呢？lct！！！并查集即可，维护联通块直径的两个端点，合并时分6中情况讨论即可，注意由于递归完左儿子后还要处理右儿子，所以左儿子中连的边都要清掉，于是并查集不能路径压缩，按秩合并即可（然而我故意把size大的合并到size小的还是A掉了）。
1 #include<iostream>
2 #include<cstring>
3 #include<cstdio>
4 #include<vector>
5 #define re register
6 #define co const
7 #define rec re co
8 #define LL long long
9 using namespace std;
10 struct edge
11 {
12 int u,v,nxt,l,r;
13 #define u(x) ed[x].u
14 #define v(x) ed[x].v
15 #define l(x) ed[x].l
16 #define r(x) ed[x].r
17 #define n(x) ed[x].nxt
18 friend bool operator < (edge a,edge b)
19 {return a.r>b.r;}
20 }ed[500010];
21 int first[500010],num_e=1;
22 #define f(x) first[x]
23 int n,m;
24 int f[200010][21],dep[200010],size[200010];
25 int ttop[200010],son[200010],dfn[200010],id[200010],cnt;
26 void dfs1(int x)
27 {
28 size[x]=1;
29 for(int i=f(x);i;i=n(i))
30 if(v(i)!=f[x][0])
31 {
32 f[v(i)][0]=x;dep[v(i)]=dep[x]+1;
33 dfs1(v(i));size[x]+=size[v(i)];
34 if(size[v(i)]>size[son[x]])son[x]=v(i);
35 }
36 }
37 void dfs2(int x,int t)
38 {
39 ttop[x]=t;dfn[x]=++cnt;id[cnt]=x;
40 if(son[x])dfs2(son[x],t);
41 for(int i=f(x);i;i=n(i))
42 if(v(i)!=f[x][0]&&v(i)!=son[x])
43 dfs2(v(i),v(i));
44 }
45 inline int LCA(int x,int y)
46 {
47 while(ttop[x]!=ttop[y])
48 {
49 if(dep[ttop[x]]>dep[ttop[y]])swap(x,y);
50 y=f[ttop[y]][0];
51 }
52 if(dep[x]>dep[y])swap(x,y);
53 return x;
54 }
55 #define st sta[top]
56 #define st2 sta2[top2]
57 #define st3 sta3[top3]
58 struct node{int id,pu,pv;}sta[500010];int top;
59 struct node2{int id,of;}sta2[500010];int top2;
60 struct node3{int id,ad;}sta3[500010];int top3;
61 vector<int> in[800010];
62 int fa[200010],u[200010],v[200010],al[200010],siz[200010];
63 int get(re int x){return fa[x]==x?x:get(fa[x]);}
64 LL lenth(re int u,re int v){return dep[u]+dep[v]-dep[LCA(u,v)]*2;}
65 void solve(re int l,re int r,rec int x,re int res)
66 {
67 int mid=(l+r)>>1,tem=top,tem2=top2,tres=res,tem3=top3;
68 for(int i=0;i<in[x].size();i++)
69 if(l(in[x][i])<=l&&r(in[x][i])>=r)
70 {
71
72 int f1=get(u(in[x][i])),f2=get(v(in[x][i]));if(f1==f2)continue;
73 int gl;
74 if(siz[f1]>siz[f2])
75 {
76 fa[f1]=f2;gl=f2;siz[f2]+=siz[f1];
77 sta[++top]=(node){f2,u[f2],v[f2]};
78 sta2[++top2]=(node2){f1,f1};
79 sta3[++top3]=(node3){f2,siz[f1]};
80 }
81 else
82 {
83 fa[f2]=f1;gl=f1;siz[f1]+=siz[f2];
84 sta[++top]=(node){f1,u[f1],v[f1]};
85 sta2[++top2]=(node2){f2,f2};
86 sta3[++top3]=(node3){f1,siz[f2]};
87 }
88 int t1=u[f1],t2=u[f2],t3=v[f1],t4=v[f2];
89 int max1=lenth(t1,t2),
90 max2=lenth(t1,t3),
91 max3=lenth(t1,t4),
92 max4=lenth(t2,t3),
93 max5=lenth(t2,t4),
94 max6=lenth(t3,t4);
95 int maxn=max(max1,max2);maxn=max(maxn,max3);
96 maxn=max(maxn,max4);maxn=max(maxn,max5);maxn=max(maxn,max6);
97 if(maxn==max1)u[gl]=t1,v[gl]=t2;
98 else if(maxn==max2)u[gl]=t1,v[gl]=t3;
99 else if(maxn==max3)u[gl]=t1,v[gl]=t4;
100 else if(maxn==max4)u[gl]=t2,v[gl]=t3;
101 else if(maxn==max5)u[gl]=t2,v[gl]=t4;
102 else if(maxn==max6)u[gl]=t3,v[gl]=t4;
103 res=max(res,maxn);
104 }
105 else
106 {
107 if(l(in[x][i])<=mid)in[x*2].push_back(in[x][i]);
108 if(r(in[x][i])> mid)in[x*2+1].push_back(in[x][i]);
109 }
110 if(l==r)
111 {
112 al[l]=res;
113 while(top>tem)u[st.id]=st.pu,v[st.id]=st.pv,top--;
114 while(top2>tem2)fa[st2.id]=st2.of,top2--;
115 while(top3>tem3)siz[st3.id]-=st3.ad,top3--;
116 res=tres;
117 return;
118 }
119 solve(l,mid,x*2,res);solve(mid+1,r,x*2+1,res);
120 while(top>tem)u[st.id]=st.pu,v[st.id]=st.pv,top--;
121 while(top2>tem2)fa[st2.id]=st2.of,top2--;
122 while(top3>tem3)siz[st3.id]-=st3.ad,top3--;
123 res=tres;
124 }
125 inline int read();
126 inline void add(rec int u,rec int v,rec int l,rec int r);
127 signed main()
128 {
129 // freopen("speed1.in","r",stdin);
130 // freopen("out.out","w",stdout);
131
132 n=read(),m=read();
133 int tu,tv,tl,tr;
134 for(re int i=1;i<n;i++)
135 {
136 tu=read(),tv=read(),tl=read(),tr=read();
137 add(tu,tv,tl,tr);add(tv,tu,tl,tr);
138 }
139 dfs1(1),dfs2(1,1);
140 for(re int i=1;i<=20;i++)
141 for(re int j=1;j<=n;j++)
142 f[j][i]=f[f[j][i-1]][i-1];
143 for(re int i=1;i<=n;i++)fa[i]=u[i]=v[i]=i,siz[i]=1;
144 for(re int i=2;i<=num_e;i+=2)in[1].push_back(i);
145 solve(1,n,1,0);
146 int q;
147 for(re int i=1;i<=m;i++)
148 {
149 q=read();
150 printf("%d\n",al[q]);
151 }
152 }
153 inline int read()
154 {
155 int s=0,f=1;char a=getchar();
156 while(a<'0'||a>'9'){if(a=='-')f=-1;a=getchar();}
157 while(a>='0'&&a<='9'){s=s*10+a-'0';a=getchar();}
158 return s*f;
159 }
160 inline void add(rec int u,rec int v,rec int l,rec int r)
161 {
162 ++num_e;
163 u(num_e)=u;
164 v(num_e)=v;
165 l(num_e)=l;
166 r(num_e)=r;
167 n(num_e)=f(u);
168 f(u)=num_e;
169 }
View Code