TokensontheTree - 题解

标签与难度

标签: 树论, 树的重心, 重链剖分思想, 贡献法, 双指针, 组合计数, 动态规划难度: 2800

题目大意喵~

主人，你好呀~！这道题是这样的喵：

我们有一棵有 $n$ 个节点的树。树上的每个节点最多可以放一个棋子，棋子分黑白两种颜色。总共有 $w$ 个白棋和 $b$ 个黑棋。

一个合法的棋子布局需要满足一个初始条件：对于任何一种颜色，所有该颜色的棋子所在的节点必须形成一个连通块。也就是说，任意两个白棋之间都有一条只由白棋节点构成的路径，黑棋同理。这其实就意味着，白棋占据了一个大小为 $w$ 的子树，黑棋占据了一个大小为 $b$ 的子树，并且这两个子树没有公共节点。

然后呢，我们可以对棋子进行一种操作：

选一个带棋子的节点 $u$ 。
选一条从 $u$ 开始的路径 $p_1, p_2, \dots, p_k$ ，其中 $p_1=u$ 。
这条路径上，除了终点 $p_k$ 是空的，前面的所有节点 $p_1, \dots, p_{k-1}$ 都必须有和 $u$ 相同颜色的棋子。
把 $p_1$ 的棋子移动到 $p_k$ 。

如果一个布局 S 可以通过若干次这样的操作变成布局 T，我们就说 S 和 T 是等价的。所有相互等价的布局构成一个等价类。

对于给定的 $w$ 和 $b$ ，我们用 $f(w, b)$ 表示所有合法布局能划分成的等价类的数量。

最终，我们需要计算下面这个式子的值，喵~

\left(\sum_{w=1}^{n-1}\sum_{b=1}^{n-w} w \cdot b \cdot f(w, b) \right) \pmod{10^9+7}

解题思路分析

这道题看起来好复杂呀，又是棋子移动，又是等价类计数，还要算一个奇怪的求和式，喵~ 但是别怕，让我来一步步拆解它！

关键性质：棋子的移动与等价类

首先，我们来分析一下棋子的移动规则。规则说，一个棋子可以“跳过”一连串同色棋子，落到路径末端的空位上。这看起来很强大，但它到底意味着什么呢？

如果一个棋子在它所在颜色连通块的叶子位置，那么它可以直接移动到相邻的空节点上。通过一系列这样的“叶子移动”，整个同色棋子构成的子树就可以在树上“流动”，像变形虫一样，改变形状和位置，但始终保持连通和大小不变。

那非叶子节点的移动呢？如果一个棋子 $u$ 不是叶子，移动它可能会导致它原来的颜色块断开。题目描述里“must have been a path”的措辞有点微妙，但通常这类问题都要求在操作过程中保持某些性质不变。如果我们假设连通性在移动后也必须保持，那么只有叶子棋子可以移动。如果连通性可以被破坏，那么任何一个 $w$ 个节点的连通块（ $w$ -子树）都可以变成任何另一个 $w$ -子树，只要有足够的空位。

经过一番思考和对题目性质的揣摩，我们可以得出一个关键结论：两个布局 (T_w, T_b) 和 (T'_w, T'_b)（其中 T 代表棋子构成的子树）是等价的，当且仅当它们的“相对拓扑关系”是相同的。

`f(w, b)` 的本质是什么？

f(w, b) 是等价类的数量。这取决于白色子树和黑色子树的相对位置关系有多少种“不可逾越”的模式。

想象一下，白色子树 T_w 和黑色子树 T_b 在树上。它们之间就像两个国家，被一些空节点（无人区）隔开。它们能在自己的领地里自由活动，但它们能互相交换位置吗？

在树这种结构里，要从 A 点到 B 点只有唯一路径。如果 T_b 在 T_w “通往”树的某个部分的必经之路上，T_w 就无法“穿过”T_b。

这就引出了一个核心问题：T_w 和 T_b 的角色是否对称？也就是说，白棋和黑棋的布局模式是否可以互换？

假设 $w \ge b$ 。如果黑棋（小的那一坨）可以整个移动到一个足够大的空地（大小至少为 $b$ ）里暂时“躲起来”，那么白色棋子（大的那一坨）就可以自由移动到黑棋原来的位置。之后黑棋再从“避难所”里出来，移动到白棋空出来的地盘。这样，它们就完成了位置的交换。

所以，我们猜测：

f(w, b) = 1: 如果对于任意一种 T_w 和 T_b 的布局，我们总能找到一个大小至少为 $\min(w, b)$ 的空连通块，让小的那一坨棋子躲进去。这时，黑白棋的位置关系是灵活的，所有布局都属于同一个等价类。
f(w, b) = 2: 如果存在一种布局，使得不管怎么放，都找不到这么大的“避难所”。那么黑白棋的位置就被“锁死”了。比如，白棋总在“左边”，黑棋总在“右边”，这是一种等价类；反过来，白棋在“右边”，黑棋在“左边”，是另一种无法到达的等价类。

如何找到最佳“避难所”？

为了让空地尽可能大，我们应该把 T_w 和 T_b 摆放得尽可能“紧凑”。在树上，最“紧凑”的结构就是沿着一条路径排列。

这启发我们使用树的重心和类似重链剖分的思想来分析。

找到树的重心 rt：以重心为根，可以使得所有子树的大小都相对均衡，这在处理和子树大小相关的问题时非常有用。
构造一条“长链”：我们从重心 rt 出发，分别走向它最大和次大的子树，沿着每条路上的“最重”的儿子一直走到底，形成两条重链。把这两条重链在重心处拼接起来，就得到了一条贯穿树的最核心的“长链”或者说“主轴”。
分析主轴：这条主轴 seq 把树分成了几部分：主轴上的点，以及许多“挂”在主轴节点上的小分支。对于主轴上的每个点 seq[i]，我们可以预处理出它“左边”的节点总数 vl[i]， “右边”的节点总数 vr[i]，以及挂在它身上的最大分支的大小 vc[i]。

贡献法与双指针

直接计算那个二重求和非常困难。我们可以转换思路，枚举其中一个变量（比如 $w$ ），然后计算所有相关的 $b$ 对答案的贡献。我们不妨设 $w \ge b$ ，并称 $w$ 为 big， $b$ 为 small。

我们从 big = 1 开始递增枚举。对于每个 big：

确定 big 棋子的可能区域：big 个棋子要形成一个连通块，至少需要 big 个节点。在我们的主轴模型上，如果想把 big 个棋子放在主轴左侧，那么左侧的节点总数 vl[l] 必须大于等于 big。同理 vr[r] 也要大于等于 big。
动态调整主轴：我们用双指针 l 和 r 表示当前考虑的主轴有效范围 seq[l...r]。如果 vl[l] < big，说明左侧空间不够，l 指针就必须右移，放弃一小段主轴。r 指针同理。这样，l 和 r 就圈定了一个对当前 big 来说“有意义”的中心区域。
寻找最大“避难所” mx：在这个中心区域 seq[l...r] 内，能提供给 small 棋子“避难”的最大空地，就是挂在 seq[l...r] 上的最大分支，即 mx = max(vc[i]) for i from l to r。我们可以用一个 multiset 实时维护这个最大值。
计算贡献：现在，对于固定的 big，和所有 small <= big，我们可以根据 mx 的大小来确定 f(big, small) 的值并计算贡献。
- 当 small <= mx 时，存在足够大的避难所，f(big, small) = 1。
- 当 small > mx 时，避难所不够大，f(big, small) = 2。
我们可以用等差数列求和公式，一次性计算出所有 small 的贡献，避免了内层循环。
处理边界情况：当 l 和 r 相遇或交错，主循环就结束了。这表示对于更大的 big，棋子已经无法被限制在重心的某一侧了，它们必然会跨越重心。这些情况需要单独处理，此时 f(w,b) 总是 2，因为一个棋子群总是会把另一个“堵”在某个子树里。我们可以用一个 dfs 来计算这部分的贡献。

通过这个精妙的流程，我们把一个复杂的计数问题转化为了一个带双指针的迭代问题，大大降低了复杂度，喵~

代码实现

cpp

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>
#include <set>

using namespace std;

typedef long long ll;

const int MOD = 1e9 + 7;

// 图的邻接表
vector<int> adj[200005];
// sz[u]: 以u为根的子树大小; dep[u]: 节点u的深度
int sz[200005], dep[200005];
// vl[i], vr[i]: 长链上第i个节点左右两侧的节点数
// vc[i]: 挂在长链第i个节点上的最大非长链子树大小
int vl[200005], vr[200005], vc[200005];
// center_cand: <最大子树大小, 重心ID>
pair<int, int> center_cand;
// n: 节点总数; ans: 最终答案
int n;
ll ans;

// 第一次DFS：计算子树大小，并找到树的重心
void find_centroid_dfs(int u, int p, int d) {
    sz[u] = 1;
    dep[u] = d;
    int max_child_sz = 0;
    for (int v : adj[u]) {
        if (v != p) {
            find_centroid_dfs(v, u, d + 1);
            sz[u] += sz[v];
            max_child_sz = max(max_child_sz, sz[v]);
        }
    }
    int max_comp_sz = max(max_child_sz, n - sz[u]);
    center_cand = min(center_cand, {max_comp_sz, u});
}

// 辅助函数，获取以v为根的子树大小（当p是v的父节点时）
// 这是为了在以任意点为根的DFS结果中，方便地得到以重心为根时的子树大小
int get_subtree_size(int v, int p) {
    if (dep[v] > dep[p]) {
        return sz[v];
    }
    return n - sz[p];
}

// 第二次DFS：从指定节点出发，构造重链
void build_heavy_path_dfs(int u, int p, vector<int>& path) {
    path.push_back(u);
    int heavy_child = -1;
    int max_sz = 0;
    for (int v : adj[u]) {
        if (v != p) {
            int child_sz = get_subtree_size(v, u);
            if (child_sz > max_sz) {
                max_sz = child_sz;
                heavy_child = v;
            }
        }
    }
    if (heavy_child != -1) {
        build_heavy_path_dfs(heavy_child, u, path);
    }
}

// 等差数列求和: (x + ... + y)
ll sum_arith_seq(ll x, ll y) {
    if (x > y) return 0;
    return (x + y) % MOD * ((y - x + 1) % MOD) % MOD * ((MOD + 1) / 2) % MOD;
}

// 第三次DFS：处理`big`值很大，棋子必须跨越重心的情况
void calculate_tail_contribution_dfs(int u, int p, int min_big_size) {
    int parent_comp_size = get_subtree_size(p, u);
    int my_comp_size = n - parent_comp_size;

    // w在父侧, b在u子树内: w的范围[min_big_size, parent_comp_size], b的范围[1, my_comp_size]
    // 贡献是 2 * (sum w) * (sum b), f=2
    ll term1 = sum_arith_seq(min_big_size, parent_comp_size);
    ll term2 = sum_arith_seq(1, my_comp_size);
    ans = (ans + 2 * term1 % MOD * term2 % MOD) % MOD;

    // b在父侧, w在u子树内: b的范围[1, parent_comp_size], w的范围[min_big_size, my_comp_size]
    // 贡献是 2 * (sum w) * (sum b), f=2
    term1 = sum_arith_seq(min_big_size, my_comp_size);
    term2 = sum_arith_seq(1, parent_comp_size);
    ans = (ans + 2 * term1 % MOD * term2 % MOD) % MOD;

    for (int v : adj[u]) {
        if (v != p) {
            calculate_tail_contribution_dfs(v, u, parent_comp_size + 1);
        }
    }
}


void solve() {
    cin >> n;
    for (int i = 0; i < n; ++i) adj[i].clear();
    for (int i = 1; i < n; ++i) {
        int p;
        cin >> p;
        --p;
        adj[i].push_back(p);
        adj[p].push_back(i);
    }

    // 1. 寻找重心
    center_cand = {n, -1};
    find_centroid_dfs(0, -1, 0);
    int root = center_cand.second;
    
    // 重新以重心为根计算深度和子树大小，方便后续计算
    find_centroid_dfs(root, -1, 0);

    // 2. 构造长链
    vector<int> path1, path2;
    int heavy_child1 = -1, heavy_child2 = -1;
    int max_sz1 = 0, max_sz2 = 0;
    for(int v : adj[root]) {
        int child_sz = sz[v];
        if (child_sz > max_sz1) {
            max_sz2 = max_sz1;
            heavy_child2 = heavy_child1;
            max_sz1 = child_sz;
            heavy_child1 = v;
        } else if (child_sz > max_sz2) {
            max_sz2 = child_sz;
            heavy_child2 = v;
        }
    }

    if (heavy_child1 != -1) build_heavy_path_dfs(heavy_child1, root, path1);
    if (heavy_child2 != -1) build_heavy_path_dfs(heavy_child2, root, path2);
    
    vector<int> long_path = path2;
    reverse(long_path.begin(), long_path.end());
    long_path.push_back(root);
    long_path.insert(long_path.end(), path1.begin(), path1.end());

    // 3. 预处理长链信息
    multiset<int> hanging_subtrees;
    for (int i = 0; i < long_path.size(); ++i) {
        int u = long_path[i];
        vl[i] = vc[i] = vr[i] = 0;
        int p_left = (i > 0) ? long_path[i - 1] : -1;
        int p_right = (i + 1 < long_path.size()) ? long_path[i + 1] : -1;

        int parent_on_path = (dep[p_left] < dep[u]) ? p_left : p_right;
        if(u == root) parent_on_path = -1;

        int current_vl = 0;
        if(p_left != -1) current_vl = (dep[p_left] > dep[u]) ? sz[p_left] : n - sz[u];

        vl[i] = (i > 0) ? vl[i-1] + current_vl : 0;
        
        int current_vc = 0;
        for (int v : adj[u]) {
            if (v != p_left && v != p_right) {
                 current_vc = max(current_vc, get_subtree_size(v, u));
            }
        }
        vc[i] = current_vc;
        hanging_subtrees.insert(vc[i]);
    }
    for(int i = long_path.size() - 1; i >= 0; --i) {
        int u = long_path[i];
        int p_right = (i + 1 < long_path.size()) ? long_path[i+1] : -1;
        int current_vr = 0;
        if(p_right != -1) current_vr = (dep[p_right] > dep[u]) ? sz[p_right] : n - sz[u];
        vr[i] = (i < long_path.size() - 1) ? vr[i+1] + current_vr : 0;
    }


    // 4. 双指针 + 贡献法计算
    ans = 0;
    int l = 0, r = long_path.size() - 1;
    int big_size = 1;
    for (;; ++big_size) {
        while (l <= r && vl[l] < big_size) {
            hanging_subtrees.erase(hanging_subtrees.find(vc[l]));
            l++;
        }
        while (l <= r && vr[r] < big_size) {
            hanging_subtrees.erase(hanging_subtrees.find(vc[r]));
            r--;
        }

        if (l > r) break;

        int max_escape_size = hanging_subtrees.empty() ? 0 : *hanging_subtrees.rbegin();

        // 贡献来自 (w,b) 和 (b,w) 两部分，这里统一计算
        // w=big, b=small
        // Case 1: w=b=big_size
        ll f_val = (max_escape_size >= big_size) ? 1 : 2;
        ans = (ans + (ll)big_size * big_size % MOD * f_val) % MOD;

        // Case 2: w=big_size, b < big_size
        // 2a: 1 <= b <= min(big_size-1, max_escape_size). f=1.
        int mobile_small_max = min(big_size - 1, max_escape_size);
        ll term = (ll)big_size * sum_arith_seq(1, mobile_small_max) % MOD;
        ans = (ans + 2 * term) % MOD;

        // 2b: max_escape_size < b <= big_size-1. f=2.
        int stuck_small_min = max_escape_size + 1;
        int stuck_small_max = big_size - 1;
        term = (ll)big_size * sum_arith_seq(stuck_small_min, stuck_small_max) % MOD;
        ans = (ans + 2 * 2 * term) % MOD;
    }
    
    // 5. 处理剩余的大 `big_size` 情况
    for (int v : adj[root]) {
        calculate_tail_contribution_dfs(v, root, big_size);
    }

    cout << ans << endl;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

复杂度分析

时间复杂度: $O(N \log N)$ 或 $O(N)$ 。
- 寻找重心和构造长链的 DFS 过程是 $O(N)$ 的。
- 主循环中，big_size 从 1 增长到 $N$ 。双指针 l 和 r 在整个过程中只会单向移动，总共移动 $O(N)$ 次。multiset 的操作是 $O(\log N)$ 的。所以这部分是 $O(N \log N)$ 。
- 最后的 dfs3 递归，每个节点只会被访问一次，所以是 $O(N)$ 。
- 总体来看，瓶颈在于主循环中的 multiset 操作，所以是 $O(N \log N)$ 。如果用其他数据结构（如基数排序思想的桶）来维护最大值，可以优化到 $O(N)$ 。
空间复杂度: $O(N)$ 。
- 主要是邻接表、各种辅助数组（sz, dep, vl, vr, vc）以及长链 long_path 占用的空间，都是线性的，喵~

知识点总结

这真是一道融合了多种思想的超级好题呀，喵！解开它之后感觉自己的小脑袋瓜都变聪明了呢~

问题转化: 核心在于理解 f(w, b) 的含义。通过分析棋子移动的本质，将复杂的等价关系问题转化为一个关于拓扑位置是否可以交换的几何问题。
树的重心: 面对与子树大小相关的树上问题，第一时间想到树的重心是一个非常好的习惯！它能帮助我们找到一个“平衡”的切入点来分解问题。
重链剖分思想: 我们没有用完整的重链剖分，但构造“长链”的思想是其精髓。通过找到树的“主轴”，可以将树结构简化为“链+挂件”的模型，方便我们进行分析和双指针操作。
贡献法/改变求和顺序: 当遇到难以直接计算的多重求和时，改变求和顺序，或者说使用贡献法，是一个强大的武器。我们枚举 w，然后批量计算所有 b 的贡献，而不是一个一个地算 f(w,b)。
双指针: 在长链上使用双指针 l, r 来动态维护一个“核心区间”，是处理与大小限制相关的区间问题的常用技巧。
组合计数: 最终的贡献计算涉及到了等差数列求和，这是组合数学中的基本功，要熟练掌握哦。

总之，解决这道题需要对树的性质有深刻的理解，并能灵活地组合运用多种算法思想。主人你做出来了吗？没做出来也没关系，和我一起学习，每天都能进步一点点哦，喵~！

TokensontheTree - 题解 ​

标签与难度 ​

题目大意喵~ ​

解题思路分析 ​

关键性质：棋子的移动与等价类 ​

f(w, b) 的本质是什么？ ​

如何找到最佳“避难所”？ ​

贡献法与双指针 ​

代码实现 ​

复杂度分析 ​

知识点总结 ​