@[cosf](/user/516725)
你的 lca 是不是炸了？
我在你的代码中使用了以下代码测了一下你的 lca，结果无论我输入怎样的两个数，你的 lca 返回的都是第二个数。
这是我用于检验你的 lca 的代码，置于输入的后方。
```
while(1){
int u,v;
cin>>u>>v;
cout<<DST::lca(u,v)<<"\n";
}
```
by 潘德理2010 @ 2023-11-20 20:47:34
我不会 lca，所以你自己调吧
by 潘德理2010 @ 2023-11-20 20:48:05
@[潘德理2010](/user/572133) 我本地测就是真的 lca 啊。
（前两个为点，后一个为 lca）
```cpp
3 5 3
4 1 1
3 5 3
4 5 3
1 3 1
3 4 3
3 5 3
1 3 1
4 5 3
5 3 3
1 4 1
5 4 3
2 1 1
3 2 1
3 1 1
4 5 3
5 2 1
...
```
by cosf @ 2023-11-20 20:56:49
这个是我拿来测的代码，你试着跑一下
```
#include <iostream>
#include <vector>
using namespace std;
#define MAXN 100005
#define MAXZ 100001
vector<int> e[MAXN];
int n, m;
namespace SGT {
struct Tree {
int l, r;
int mc, mv;
} t[MAXN << 6];
int rt[MAXN];
int idx = 0;
void pushup(int p) {
if (t[t[p].l].mv >= t[t[p].r].mv) {
t[p].mv = t[t[p].l].mv;
t[p].mc = t[t[p].l].mc;
} else {
t[p].mv = t[t[p].r].mv;
t[p].mc = t[t[p].r].mc;
}
}
void update(int &p, int l, int r, int q, int v) { // 给 q 位置加上 v
if (!p) {
p = ++idx;
}
if (l == r) {
t[p].mv += v;
if (t[p].mv) {
t[p].mc = l;
} else {
t[p].mc = 0;
}
return;
}
int mid = (l + r) >> 1;
if (mid >= q) {
update(t[p].l, l, mid, q, v);
} else {
update(t[p].r, mid + 1, r, q, v);
}
pushup(p);
}
void merge(int &a, int b, int l, int r) { // 将 b 与 a 合并至 a
if (!a) {
a = b;
return;
}
if (!b) {
return;
}
if (l == r) {
t[a].mv += t[b].mv;
if (t[a].mv) {
t[a].mc = l;
} else {
t[a].mc = 0;
}
return;
}
int mid = (l + r) >> 1;
merge(t[a].l, t[b].l, l, mid);
merge(t[a].r, t[b].r, mid + 1, r);
pushup(a);
}
}
namespace DST { // 树剖
int siz[MAXN], son[MAXN], fa[MAXN];
int dep[MAXN];
int top[MAXN];
void dfs1(int p, int f) {
fa[p] = f;
dep[p] = dep[f] + 1;
siz[p] = 1;
for (int u : e[p]) {
if (u == f) {
continue;
}
dfs1(u, p);
siz[p] += siz[u];
if (siz[u] > siz[son[p]]) {
son[p] = u;
}
}
}
void dfs2(int p, int t) { // 树剖
top[p] = t;
if (!son[p]) {
return;
}
dfs2(son[p], t);
for (int u : e[p]) {
if (u == fa[p] || u == son[p]) {
continue;
}
dfs2(u, u);
}
}
int lca(int u, int v) {
while (top[u] != top[v]) {
if (dep[top[u]] < dep[top[v]]) {
swap(u, v);
}
u = fa[top[u]];
}
if (dep[u] < dep[v]) {
swap(u, v);
}
return v;
}
void dfs3(int p) { // 合并
for (int u : e[p]) {
if (u == fa[p]) {
continue;
}
dfs3(u);
}
for (int u : e[p]) {
if (u == fa[p]) {
continue;
}
SGT::merge(SGT::rt[p], SGT::rt[u], 1, MAXZ);
}
}
}
// using namespace SGT;
// using namespace DST;
int main() {
// freopen("P4556_7.in", "r", stdin);
// freopen("P4556.out", "w", stdout);
cin >> n >> m;
for (int i = 1; i < n; i++) {
int u, v;
cin >> u >> v;
e[u].push_back(v);
e[v].push_back(u);
}
while(1){
int u,v;
cin>>u>>v;
cout<<DST::lca(u,v)<<"\n";
}
DST::dfs1(1, 0);
DST::dfs2(1, 1);
for (int i = 1; i <= m; i++) {
int u, v, z;
cin >> u >> v >> z;
SGT::update(SGT::rt[u], 1, MAXZ, z, 1);
SGT::update(SGT::rt[v], 1, MAXZ, z, 1);
int l = DST::lca(u, v);
SGT::update(SGT::rt[l], 1, MAXZ, z, -1);
SGT::update(SGT::rt[DST::fa[l]], 1, MAXZ, z, -1);
}
DST::dfs3(1);
for (int i = 1; i <= n; i++) {
cout << SGT::t[SGT::rt[i]].mc;
cout << endl;
}
return 0;
}
```
by 潘德理2010 @ 2023-11-20 21:12:05
@[cosf](/user/516725)
by 潘德理2010 @ 2023-11-20 21:12:22
@[潘德理2010](/user/572133) 都没跑树剖你求 lca 求啥？
by cosf @ 2023-11-20 21:18:47
@[cosf](/user/516725)
发现一个问题：
你的程序好像栽在了 1 号节点上。
hack：
```
7 4
1 2
1 3
2 4
2 5
3 6
3 7
1 4 1
1 5 2
1 6 2
1 7 1
```
Your Output:
```
1
1
1
1
2
1
1
```
Correct Output:
```
1
1
1
1
2
2
1
```
by 潘德理2010 @ 2023-11-20 21:48:45
我下载了个数据发现错的那一行第一个点刚好是 1。
我能力不够，调不了树剖这种东西，你自己看着调吧。
by 潘德理2010 @ 2023-11-20 21:51:23