啊？这么复杂，这不是并查集吗。。。
by Fractured_Angel @ 2023-11-11 18:28:57
@[the_long_way_to_dp](/user/837888) 重构树可以在线做。
by lzyqwq @ 2023-11-11 18:32:01
@[Ailuomangacencei](/user/426187) $(sz_u+1)/2$ 我不知道对不对，你其实可以直接维护每个子树的叶子个数的
by lzyqwq @ 2023-11-11 18:32:48
哦，纠正一下，我忘记减去自己了，所以应该是(sz[u] - 1) / 2 (大概？）
by Ailuomangacencei @ 2023-11-11 18:39:12
求助，T了第8个点
```cpp
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
int n, Q;
int fa[N], top[N], sz[N], nw[N];
struct E{
int u, v, w;
bool operator < (const E &x) const {
return w > x.w;
}
}edge[N];int idx;
inline int find_top(int x){
if (x == top[x]) return x;
return top[x] = find_top(top[x]);
}
void EK_kruskal(){
for (int i = 0;i < n * 2; ++ i){
top[i] = i; sz[i] = 1;
}
for (int i = 1;i < n; ++ i){
int u = edge[i].u, v = edge[i].v, w = edge[i].w;
if (find_top(u) == find_top(v)) continue;
int nwp = n + i; nw[nwp] = w;
sz[nwp] += sz[top[u]] + sz[top[v]];
fa[top[u]] = fa[top[v]] = nwp;
top[top[u]] = top[top[v]] = nwp;
}
}
inline void add(int u, int v, int w){
edge[++idx].u = u;
edge[idx].v = v;
edge[idx].w = w;
}
int main(){
scanf("%d%d", &n, &Q);
for (int i = 1;i < n; ++ i){
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
add(u, v, w);
}
sort(edge + 1, edge + n);
EK_kruskal();
fa[0] = n * 2; nw[n * 2] = -1;
while (Q --){
int k, v;scanf("%d%d", &k, &v);
while (nw[fa[v]] >= k) v = fa[v];
printf("%d\n", (sz[v] - 1) >> 1);
}
return 0;
}
```
gg,这怎么被卡的
其他点都是100ms以下
by Ailuomangacencei @ 2023-11-11 19:11:46
警钟长鸣吧
好像确实可以把重构树卡成一条链
by Ailuomangacencei @ 2023-11-11 19:14:09
是时候请出倍增来优化了
by Ailuomangacencei @ 2023-11-11 19:15:09
OK,倍增解决
给大家分享一下
```cpp
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
int n, Q;
int fa[N][20], top[N], sz[N], nw[N];
struct E{
int u, v, w;
bool operator < (const E &x) const {
return w > x.w;
}
}edge[N];int idx;
inline int find_top(int x){
if (x == top[x]) return x;
return top[x] = find_top(top[x]);
}
void EK_kruskal(){
for (int i = 0;i < n * 2; ++ i){
top[i] = i; sz[i] = 1;
}
for (int i = 1;i < n; ++ i){
int u = edge[i].u, v = edge[i].v, w = edge[i].w;
if (find_top(u) == find_top(v)) continue;
int nwp = n + i; nw[nwp] = w;
sz[nwp] += sz[top[u]] + sz[top[v]];
fa[top[u]][0] = fa[top[v]][0] = nwp;
top[top[u]] = top[top[v]] = nwp;
}
for (int i = 1;i < 20; ++ i)
for (int j = 1;j < n * 2; ++ j)
fa[j][i] = fa[fa[j][i - 1]][i - 1];
}
inline void add(int u, int v, int w){
edge[++idx].u = u;
edge[idx].v = v;
edge[idx].w = w;
}
int main(){
scanf("%d%d", &n, &Q);
for (int i = 1;i < n; ++ i){
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
add(u, v, w);
}
sort(edge + 1, edge + n);
EK_kruskal();
while (Q --){
int k, v;scanf("%d%d", &k, &v);
for (int i = 19;i >= 0; -- i)
if (nw[fa[v][i]] >= k)
v = fa[v][i];
printf("%d\n", (sz[v] - 1) >> 1);
}
return 0;
}
```
by Ailuomangacencei @ 2023-11-11 19:19:07
@[Ailuomangacencei](/user/426187) 其实4年前的题解就有你这种做法了
by arrowpoint @ 2024-05-18 19:19:55