# 我是这样写的：
#include <cstdio>
#include <set>
typedef long long LL;
const int MN = 100005;
int N, M;
int h[MN], nxt[MN * 2], to[MN * 2], w[MN * 2], tot;
inline void ins(int x, int y, int z) {
nxt[++tot] = h[x], to[tot] = y, w[tot] = z, h[x] = tot;
}
int dfn[MN], idf[MN], dfc;
int dep[MN], faz[MN][17];
LL dis[MN];
void DFS(int u, int fz) {
dfn[u] = ++dfc; idf[dfc] = u; dep[u] = dep[faz[u][0] = fz] + 1;
for (int j = 1; 1 << j < dep[u]; ++j) faz[u][j] = faz[faz[u][j - 1]][j - 1];
for (int i = h[u]; i; i = nxt[i]) if (to[i] != fz) dis[to[i]] = dis[u] + w[i], DFS(to[i], u);
}
inline int lca(int x, int y) {
if (dep[x] < dep[y]) std::swap(x, y);
for (int d = dep[x] - dep[y], j = 0; d; d >>= 1, ++j)
if (d & 1) x = faz[x][j];
if (x == y) return x;
for (int j = 16; ~j; --j) if (faz[x][j] != faz[y][j])
x = faz[x][j], y = faz[y][j];
return faz[x][0];
}
inline LL dist(int x, int y) { return dis[x] + dis[y] - 2 * dis[lca(x, y)]; }
bool vis[MN];
std::set<int> st;
std::set<int>::iterator it;
LL Ans;
int main() {
scanf("%d%d", &N, &M);
for (int i = 1, x, y, z; i < N; ++i) {
scanf("%d%d%d", &x, &y, &z);
ins(x, y, z), ins(y, x, z);
}
DFS(1, 0);
for (int m = 1, x, y, z; m <= M; ++m) {
scanf("%d", &x);
x = dfn[x];
if (!vis[idf[x]]) st.insert(x);
y = idf[(it = st.lower_bound(x)) == st.begin() ? *--st.end() : *--it];
z = idf[(it = st.upper_bound(x)) == st.end() ? *st.begin() : *it];
if (vis[idf[x]]) st.erase(x);
x = idf[x];
LL d = dist(x, y) + dist(x, z) - dist(y, z);
if (!vis[x]) vis[x] = 1, Ans += d;
else vis[x] = 0, Ans -= d;
printf("%lld\n", Ans);
}
return 0;
}
by 陈启旺 @ 2019-04-09 21:08:46
@[陈启旺](/space/show?uid=180322) 十分感谢dalao的帮助orz
最后检查发现是倍增求LCA写炸了，窝太菜了qwq
by kkxhh @ 2019-04-09 21:12:28
之前我是这样写的，也行。
```
#include <bits/stdc++.h>
#define lb lower_bound
#define ub upper_bound
using namespace std;
typedef long long ll;
const int N = 100005, M = (N << 1), K = 21;
int n, q, ecnt = 0, idx, to[M], nxt[M], fir[N], depth[N], fa[N][K], dfn[N], pos[N];
ll dis[N], len[M], ans; bool vis[N]; set <int> S;
template <class T> void rd(T &x) {
char c = getchar(); int f = 1; x = 0;
for (; !isdigit(c); c = getchar()) if (c == '-') f = -1;
for (; isdigit(c); c = getchar()) x = x * 10 + c - '0';
x *= f;
}
void ae(int u, int v, ll w) {to[++ecnt] = v; len[ecnt] = w; nxt[ecnt] = fir[u]; fir[u] = ecnt;}
int lca(int u, int v) {
int i; if (depth[u] < depth[v]) swap(u, v);
for (i = 20; ~i; --i) if (depth[fa[u][i]] >= depth[v]) u = fa[u][i];
if (u == v) return u;
for (i = 20; ~i; --i) if (fa[u][i] != fa[v][i]) u = fa[u][i], v = fa[v][i];
return fa[u][0];
}
ll calc(int u, int v) {return dis[u] + dis[v] - dis[lca(u, v)] * 2;}
void dfs(int u, int dep, int f) {
int i; dfn[u] = ++idx; pos[idx] = u; depth[u] = dep; fa[u][0] = f;
for (i = fir[u]; i; i = nxt[i]) {
int v = to[i], w = len[i];
if (v != f) dis[v] = dis[u] + w, dfs(v, dep + 1, u);
}
}
int main() {
int i, j; rd(n); rd(q);
for (i = 1; i < n; ++i) {
int u, v; ll w; rd(u); rd(v); rd(w);
ae(u, v, w); ae(v, u, w);
}
dfs(1, 1, 0); S.insert(-1); S.insert(999999);
for (i = 1; i <= 20; ++i)
for (j = 1; j <= n; ++j) fa[j][i] = fa[fa[j][i - 1]][i - 1];
for (i = 1; i <= q; ++i) {
int x, p, l, r; ll tmp = 0; rd(x);
if (!vis[x]) S.insert(dfn[x]), p = 1; else S.erase(dfn[x]), p = -1;
vis[x] ^= 1; l = *--S.lb(dfn[x]); r = *S.ub(dfn[x]);
if (l != -1) ans += calc(pos[l], x) * p; if (r != 999999) ans += calc(pos[r], x) * p;
if (l != -1 && r != 999999) ans -= calc(pos[l], pos[r]) * p;
if (S.size() != 2) tmp = calc(pos[*++S.begin()], pos[*--S.lb(999999)]);
printf("%lld\n", ans + tmp);
}
return 0;
}
```
by 陈启旺 @ 2019-04-09 21:18:21
@[陈启旺](/space/show?uid=180322) 好的非常谢谢您qwq
真的非常谢谢您还抽空把这题切了qwq
by kkxhh @ 2019-04-09 21:21:42
不用谢
by 陈启旺 @ 2019-04-09 21:23:24
~~话说我是不是被耍了~~
~~完了要沦为后来做这道题的人的笑柄了~~
by kkxhh @ 2019-04-09 21:38:56
dalao,能具体说说您哪里错了，改了哪里吗？（因为我也全WA）
by 红色OI再临 @ 2019-06-03 21:05:01