题解 P5666 【树的重心【民间数据】】

先将树变成以 $1$ 为根的有根树，并约定 $T(u)$ 为 $u$ 的子树，$T$ 为整棵树，$p(u,T)$ 表示 $u$ 是 $T$ 的重心 ---- 考虑一些简单的手法： $$ \begin{aligned} & \sum_{(fa_u,u)\in E} \big(\sum_{p(x,T(u))} x + \sum_{p(y,T-T(u))} \big) \\ & = \sum_x x\sum_{u\not= 1} [p(x,T(u))]+\sum_x x\sum_{u\not= 1} [p(x,T-T(u))] \end{aligned} $$ ---- 考虑研究若 $p(x,T(u))$，则 $x,u$ 满足什么性质。 设 $wson$ 为 $x$ 的 $siz$ 最大的儿子。 事实上 $p(x,T(u))$ 当且仅当： $$ \left\{ \begin{aligned} & x\in T(u) \\ & siz_{wson}\le \lfloor \frac{siz_u}{2}\rfloor \\ & siz_u-siz_x\le \lfloor \frac{siz_u}{2}\rfloor \end{aligned} \right. $$ 考虑到 $\forall x\in Z$，$x\le \lfloor a\rfloor \Leftrightarrow x\le a$，因此后两个式子直接化为 $$ 2siz_{wson}\le siz_u\le 2siz_x$$ ---- 考虑研究若 $p(x,T-T(u))$，则 $x,u$ 满足什么性质。 ### Situation 1 首先考虑 $u\in T(x)-\{x\}$，设 $v$ 为 $x$ 的儿子，且 $u\in T(v)$ （显然 $v$ 存在且唯一），  设 $wson$ 为除去 $v$，$x$ 的 $siz$ 最大的儿子。（若没有，则认为 $siz_{wson}=0$） $$ \left\{ \begin{aligned} & siz_{wson}\le \lfloor \frac{n-siz_u}{2}\rfloor \\ & siz_v-siz_u\le \lfloor \frac{n-siz_u}{2}\rfloor \\ & n-siz_x\le \lfloor \frac{n-siz_u}{2}\rfloor \\ \end{aligned} \right. $$ 即 $$ 2siz_v-n\le siz_u\le \min\{n-2siz_{wson},2siz_x-n\} $$ ### Situation 2 然后考虑 $u\in T-T(x)-\{fa|p(x,T(fa))\}$ （即 $u$ 不在 $x$ 子树里也不是 $x$ 祖先），设 $wson$ 为 $x$ 的 $siz$ 最大的儿子。 $$ \left\{ \begin{aligned} & siz_{wson}\le \lfloor \frac{n-siz_u}{2}\rfloor \\ & n-siz_u-siz_x\le \lfloor \frac{n-siz_u}{2}\rfloor \\ \end{aligned} \right. $$ 也即 $$n-2siz_x \le siz_u \le n-2siz_{wson}$$ ---- 此时你已经有 40pts 了。 枚举 $x$，以计算 **Situation 1** 为例，你可以将这划分为两个这样的询问：问 $dfn_u\in [dfn_x,dfn_x+siz_x-1]$ 且 $siz_u\in [1,R](R \in [1,n])$ 的 $u$ 有多少个。 这已经十分显然了，将这 $2n$ 个询问直接离线，建一棵值域树状数组，并按照 $siz_x$ 升序依次加入，查询时直接查询区间和。 对于其它的给读者留作练习。 时间复杂度 $O(n\log n)$。 ---- ### 代码 ~~开 O2 才能过~~ ```cpp #include <cstdio> #include <algorithm> typedef long long ll; ll read() { ll ret = 0; char c = getchar(); while (c < '0' || c > '9') c = getchar(); while (c >= '0' && c <= '9') ret = ret * 10 + c - '0', c = getchar(); return ret; } inline int min(int a, int b) { return a < b ? a : b; } inline int max(int a, int b) { return a > b ? a : b; } inline int abs(int x) { return x > 0 ? x : -x; } const int MAXN = 700005; int T, N; ll ans; struct node { int v, next; } E[MAXN << 1]; int head[MAXN], Elen; void add(int u, int v) { ++Elen, E[Elen].v = v, E[Elen].next = head[u], head[u] = Elen; } int fa[MAXN], siz[MAXN], wson[MAXN], dfn[MAXN], dfncnt; void dfs(int u, int ff) { fa[u] = ff, siz[u] = 1, dfn[u] = ++dfncnt; int i; for (i = head[u]; i; i = E[i].next) { if (E[i].v == ff) continue; dfs(E[i].v, u), siz[u] += siz[E[i].v]; if (siz[E[i].v] > siz[wson[u]]) wson[u] = E[i].v; } } struct fenwick { int tree[MAXN]; inline int lowbit(int x) { return x & -x; } inline void insert(int pos, int k) { for (; pos <= N; pos += lowbit(pos)) tree[pos] += k; } inline int query(int pos) { int ret = 0; for ( ; pos; pos -= lowbit(pos)) ret += tree[pos]; return ret; } void clear() { for (int i = 1; i <= N; ++i) tree[i] = 0; } } T1, T2; struct query { int typ, val, x, k; query() {} query(int typ, int val, int x, int k) : typ(typ), val(val), x(x), k(k) {} } Q[MAXN << 4]; int Qlen; bool cmp(query q1, query q2) { return q1.k < q2.k; } int mxl[MAXN], mxr[MAXN]; void qaq(int pre, int id, int ff) { int sz = E[id].v == ff ? 0 : siz[E[id].v]; mxl[id] = max(mxl[pre], sz); if (E[id].next) qaq(id, E[id].next, ff); mxr[id] = max(mxr[E[id].next], sz); } struct data { int x, id; } D[MAXN]; bool cmpd(data d1, data d2) { return d1.x < d2.x; } int S[MAXN]; //int answer[MAXN]; int main() { #ifndef ONLINE_JUDGE freopen("test.in", "r", stdin), freopen("test.out", "w", stdout); #endif scanf("%d", &T); int i, j, prej, u, v; while (T--) { scanf("%d", &N); for (i = 1; i < N; ++i) scanf("%d%d", &u, &v), add(u, v), add(v, u); dfs(1, 0); for (i = 1; i <= N; ++i) { Q[++Qlen] = query(2, i, i, 2 * siz[i]), Q[++Qlen] = query(2, -i, i, 2 * siz[wson[i]] - 1); qaq(0, head[i], fa[i]); for (j = head[i], prej = 0; j; prej = j, j = E[j].next) { if (E[j].v == fa[i]) continue; int maxson = max(mxl[prej], mxr[E[j].next]), v = E[j].v; //printf("i = %d, v = %d, maxson = %d, l = %d, r = %d\n", i, v, maxson, mxl[prej], mxr[E[j].next]); if (min(N - 2 * maxson, 2 * siz[i] - N) >= 2 * siz[v] - N) { Q[++Qlen] = query(1, i, E[j].v, min(N - 2 * maxson, 2 * siz[i] - N)); Q[++Qlen] = query(1, -i, E[j].v, 2 * siz[v] - N - 1); } } Q[++Qlen] = query(3, i, N - 2 * siz[i], N - 2 * siz[wson[i]]); Q[++Qlen] = query(2, -i, fa[i], N - 2 * siz[wson[i]]), Q[++Qlen] = query(2, i, fa[i], N - 2 * siz[i] - 1); Q[++Qlen] = query(1, -i, i, N - 2 * siz[wson[i]]), Q[++Qlen] = query(1, i, i, N - 2 * siz[i] - 1); } //for (i = 1; i <= Qlen; ++i) printf("query(%d, %d, %d, %d)\n", Q[i].typ, Q[i].val, Q[i].x, Q[i].k); for (i = 2; i <= N; ++i) ++S[siz[i]]; for (i = 1; i <= N; ++i) S[i] += S[i - 1]; for (i = 1; i <= N; ++i) D[i].x = siz[i], D[i].id = i; std::sort(D + 1, D + N + 1, cmpd); std::sort(Q + 1, Q + Qlen + 1, cmp); j = 1; for (i = 1; i <= Qlen; ++i) { while (j <= N && D[j].x <= Q[i].k) { if (D[j].id != 1) T1.insert(dfn[D[j].id], 1), T2.insert(dfn[D[j].id], 1), T2.insert(dfn[D[j].id] + siz[D[j].id], -1); ++j; } //printf("query(%d, %d, %d, %d)\n", Q[i].typ, Q[i].val, Q[i].x, Q[i].k); int qaq; if (Q[i].typ == 3) { if (Q[i].x < 1) Q[i].x = 1; if (Q[i].k < 0) Q[i].k = 0; qaq = S[Q[i].k] - S[Q[i].x - 1]; } else if (Q[i].typ == 2) qaq = T2.query(dfn[Q[i].x]); else qaq = T1.query(dfn[Q[i].x] + siz[Q[i].x] - 1) - T1.query(dfn[Q[i].x] - 1); //printf("qaq = %d\n", qaq); ans += (ll)Q[i].val * qaq; //answer[abs(Q[i].val)] += Q[i].val * qaq; } //for (i = 1; i <= N; ++i) printf("answer[%d] = %d\n", i, answer[i] / i); printf("%lld\n", ans); T1.clear(), T2.clear(); for (i = 1; i <= N; ++i) head[i] = S[i] = wson[i] = dfn[i] = mxl[i] = mxr[i] = 0; Elen = dfncnt = Qlen = 0; ans = 0; } return 0; } ```