AC 第一个是#include <cstdio> #include <set> 你们看一下可以吗? 不是AC告诉我

guoguo  •  22小时前


include

include

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 st; std::set::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;

}


评论:

请先登录,才能进行评论