文章目录

题意思路注意代码

题意

有一棵 $n$ 个点的树，初始所有点上都有一个人，有 $m$ 个操作，每次操作使所有人都向 $p$ 点走一步（即一条边）。问最后有人的点有多少个。

$n\le 3\ast 10^5,m\le 3\ast 10^4$

思路

首先有人的节点肯定形成一棵树，因为向一个方向走只可能汇聚而不可能分散。

然后考虑一次移动的过程，显然大部分叶子没有人了（有可能还有 1 个叶子有人），然后有可能新增了一个有人的叶子。

因为叶子新增的速度非常慢，也就是说在整个移动过程中所有出现过的叶子的个数是 $O(n+m)$ 的。所以我们考虑暴力维护这棵树。

首先把所有叶子存下来，然后用可以方便删边的双向邻接表存边维护有人的点构成的树。

每次移动，对于目标点 $p$ ，找离他最近的树（有人的点构成的树，下面均以“树”代称）上的节点。假如 $p$ 就在树上，那么不会有新增点，但是假如 $p$ 是叶子的话， $p$ 也不应该被删掉。假如 $p$ 不在树上，那么找树上离 $p$ 最近的 $q$ ，把 $q$ 到 $p$ 的路径上与 $q$ 连边的点加入树中。

注意

注意细节。其实思路真的不难想，就是个暴力，但是对于我这种代码能力不足的人，比赛的三个半小时就没有办法调出这道题。

还有就是对拍很重要，这种细节题，和暴力对拍次次出问题，对于调试来说效果拔群。

代码

留下了调试。调试才是此题重点 qwq。

#include<bits/stdc++.h> using namespace std; #define pii pair<int, int> #define fi first #define se second #define mp make_pair const int N = 3e5 + 10, M = N<<3, E = 20; int n, m; struct G { int ecnt, pre[M], nxt[M], v[M]; void clear(int n){ ecnt = n|1; } void add_dir(int _u, int _v){ v[++ecnt] = _v; nxt[ecnt] = nxt[_u]; pre[ecnt] = _u; pre[nxt[_u]] = ecnt; nxt[_u] = ecnt; } void add_undir(int _u, int _v){ add_dir(_u, _v); add_dir(_v, _u); } void remove(int i){ nxt[pre[i]] = nxt[i]; pre[nxt[i]] = pre[i]; nxt[i] = pre[i] = 0; } }g; int dep[N], f[N][E]; int root, siz, leaf[N], ln, dgr[N]; int tmp[N], tn; bool vis[N]; template<class T>inline void read(T &x){ x = 0; bool fl = 0; char c = getchar(); while (!isdigit(c)){if (c == '-') fl = 1; c = getchar();} while (isdigit(c)){x = (x<<3)+(x<<1)+c-'0'; c = getchar();} if (fl) x = -x; } void dfs(int u, int fa) { dep[u] = dep[fa]+1; f[u][0] = fa; for (int i = 1; i < E; ++ i) f[u][i] = f[f[u][i-1]][i-1]; if (dgr[u] == 1) leaf[++ln] = u; for (int i = g.nxt[u]; i; i = g.nxt[i]) if (g.v[i] != fa) dfs(g.v[i], u); } int lca(int x, int y) { if (dep[x] < dep[y]) swap(x, y); for (int i = E-1; i >= 0; -- i) if (dep[f[x][i]] >= dep[y]) x = f[x][i]; if (x == y) return x; for (int i = E-1; i >= 0; -- i) if (f[x][i] != f[y][i]) x = f[x][i], y = f[y][i]; return f[x][0]; } int lca_son(int x, int y) { if (dep[x] < dep[y]) swap(x, y); for (int i = E-1; i >= 0; -- i) if (dep[f[x][i]] > dep[y]) x = f[x][i]; return x; } pii get_q(int p) { if (dgr[p]) return mp(p, -1); for (int i = E-1; i >= 0; -- i) if (!dgr[f[p][i]] && dep[f[p][i]] >= dep[root]) p = f[p][i]; if (dgr[f[p][0]]) return mp(f[p][0], 1); else return mp(root, 0); } void solve(int p) { pii pp = get_q(p); int q = pp.fi, opt = pp.se; tn = 0; // cout << p << " " << q << " " << opt << endl; for (int i = 1; i <= ln; ++ i){ if (leaf[i] == q){ if (p == q && !vis[q]) tmp[++tn] = q, vis[q] = 1; continue; } int edge = g.nxt[leaf[i]]; g.remove(edge); g.remove(edge^1); // cout << "del " << leaf[i] << " " << g.v[edge] << endl; dgr[leaf[i]]--; dgr[g.v[edge]]--; siz--; if (dgr[g.v[edge]] <= 1 && !vis[g.v[edge]] && g.v[edge] != q) tmp[++tn] = g.v[edge], vis[g.v[edge]] = 1; if (leaf[i] == root) root = g.v[edge]; } if (p != q){ if (opt == 0){ tmp[++tn] = f[q][0]; g.add_undir(f[q][0], q); dgr[q]++; dgr[f[q][0]]++; // cout << "add " << q << " " << f[q][0] << endl; if (dgr[q] == 1 && !vis[q]) tmp[++tn] = q, vis[q] = 1; siz++; root = f[q][0]; } else{ int son = lca_son(p, q); tmp[++tn] = son; g.add_undir(son, q); dgr[q]++; dgr[son]++; // cout << "add " << q << " " << son << endl; if (dgr[q] == 1 && !vis[q]) tmp[++tn] = q, vis[q] = 1; siz++; } } else if (dgr[q] == 1 && !vis[q]) tmp[++tn] = q, vis[q] = 1; ln = tn; for (int i = 1; i <= tn; ++ i) leaf[i] = tmp[i], vis[tmp[i]] = 0; } int main() { read(n); read(m); g.clear(n); memset(dgr, 0, sizeof dgr); for (int i = 1; i < n; ++ i){ int x, y; read(x); read(y); g.add_undir(x, y); ++dgr[x]; ++dgr[y]; } ln = 0; root = 1; siz = n; dfs(1, 0); for (int i = 1; i <= m; ++ i){ int p; read(p); // cout << "====================================" << endl; solve(p); if (siz <= 1) break; // for (int j = 1; j <= n; ++ j) cout << dgr[j] << " "; cout << endl; // for (int j = 1; j <= ln; ++ j) cout << leaf[j] << " "; cout << endl; // cout << root << " " << siz << endl; } if (siz < 1) siz = 1; printf("%d\n", siz); return 0; }