考虑到存在方案使得以 \(u\) 为起点还能走出原树的条件。
能发现是以 \(u\) 为根，在原树上新添加的边只会是返祖边而不会有横叉边。
这是因为如果有横叉边就肯定会在遍历到一边的点后先通过这条边走到另一边的点，就算上了这条边就不是原树了。
那么考虑 \((x, y)\)，合法的 \(u\) 需要满足什么条件。
首先先随意钦定一个树根，然后讨论一下 \(x, y\) 的关系：
- \(x, y\) 不为祖先关系。
那么 \(x, y\) 子树内的点都是合法的。 - \(x, y\) 为祖先关系
假设 \(x\) 是 \(y\) 的祖先。
那么令 \(y'\) 为是 \(y\) 的祖先且是 \(x\) 儿子的这一个点。
那么就有非 \(y'\) 子树内和 \(y\) 子树内的点是合法的。
考虑到这些都是子树的形式，用 \(\operatorname{dfn}\) 序来处理即可。
对于加减边，用一颗维护 \(\max\{cnt_i\}\) 和 \(\sum\limits [cnt_i = \max\{cnt_i\}]\) 的线段树即可。
时间复杂度 \(\mathcal{O}(n\log n)\)。
代码
#include<bits/stdc++.h>
const int maxn = 2e5 + 10;
int n;
struct node_t {
int mx, cnt;
inline node_t(int mx_ = 0, int cnt_ = 0) {
mx = mx_, cnt = cnt_;
}
inline node_t operator + (const node_t &o) const {
if (mx > o.mx)
return *this;
if (o.mx > mx)
return o;
return node_t(mx, cnt + o.cnt);
}
inline node_t operator + (const int &x) const {
return node_t(mx + x, cnt);
}
inline node_t &operator += (const int &x) {
return *this = *this + x;
}
};
node_t tr[maxn * 4];
int tag[maxn * 4];
inline void pushup(int k) {
tr[k] = tr[k << 1] + tr[k << 1 | 1];
}
inline void add(int k, int x) {
tr[k] += x, tag[k] += x;
}
inline void pushdown(int k) {
int &v = tag[k];
if (v) {
add(k << 1, v), add(k << 1 | 1, v);
v = 0;
}
}
void build(int k = 1, int l = 1, int r = n) {
if (l == r)
return tr[k] = node_t(0, 1), void();
int mid = (l + r) >> 1;
build(k << 1, l, mid), build(k << 1 | 1, mid + 1, r);
pushup(k);
}
void update(int x, int y, int v, int k = 1, int l = 1, int r = n) {
if (x > y)
return ;
if (x <= l && r <= y)
return add(k, v), void();
pushdown(k);
int mid = (l + r) >> 1;
if (x <= mid)
update(x, y, v, k << 1, l, mid);
if (mid < y)
update(x, y, v, k << 1 | 1, mid + 1, r);
pushup(k);
}
std::vector<int> son[maxn];
int dfn[maxn], dfp[maxn], rdfn[maxn], dep[maxn], siz[maxn], fa[maxn], top[maxn], dtot;
void dfs1(int u) {
dep[u] = dep[fa[u]] + 1;
siz[u] = 1;
for (int &v : son[u]) {
son[v].erase(std::find(son[v].begin(), son[v].end(), u)), fa[v] = u;
dfs1(v);
siz[u] += siz[v], siz[v] > siz[son[u][0]] && (std::swap(son[u][0], v), 1);
}
}
void dfs2(int u) {
dfn[u] = ++dtot, dfp[dtot] = u;
for (int v : son[u]) {
top[v] = v == son[u][0] ? top[u] : v;
dfs2(v);
}
rdfn[u] = dtot;
}
inline int depfa(int u, int d) {
for (; ; ) {
if (dep[top[u]] > d)
u = fa[top[u]];
else
return dfp[dfn[u] - (dep[u] - d)];
}
return -1;
}
inline void solve(int x, int y, int v) {
if (x == y)
return ;
if (dfn[x] <= dfn[y] && dfn[y] <= rdfn[x]) {
update(dfn[y], rdfn[y], v);
y = depfa(y, dep[x] + 1);
update(1, dfn[y] - 1, v), update(rdfn[y] + 1, n, v);
} else if (dfn[y] <= dfn[x] && dfn[x] <= rdfn[y]) {
update(dfn[x], rdfn[x], v);
x = depfa(x, dep[y] + 1);
update(1, dfn[x] - 1, v), update(rdfn[x] + 1, n, v);
} else {
update(dfn[x], rdfn[x], v), update(dfn[y], rdfn[y], v);
}
}
int main() {
int Q;
scanf("%d%d", &n, &Q);
for (int i = 1; i < n; i++) {
int x, y;
scanf("%d%d", &x, &y);
son[x].push_back(y), son[y].push_back(x);
}
dfs1(1), top[1] = 1, dfs2(1);
build();
std::set<std::pair<int, int> > S;
for (int c = 0; Q--; ) {
int x, y;
scanf("%d%d", &x, &y);
if (x > y)
std::swap(x, y);
std::set<std::pair<int, int> >::iterator it = S.find(std::make_pair(x, y));
if (it == S.end())
S.emplace(x, y), solve(x, y, 1), c++;
else
S.erase(it), solve(x, y, -1), c--;
printf("%d\n", tr[1].cnt * (tr[1].mx == c));
}
return 0;
}