题解：CF2117F Wildflower

Suin_tryin · 2026-03-05 13:11:18 · 题解

题面说不能有两个子树权值和相同。

先有两个发现。

• 我们考虑叶子节点，它们的子树权值和只能为 1 或 2。所以如果说这颗树有大于两个叶子节点一定会有两个叶子节点权值相同，无解。

• 一个节点到根的路径上的节点子树权值和互不相同。

对于只有一个叶子结点的树，也就是一条链，直接随便填，一定能满足要求，答案是 2^n。

对于有两个叶子节点的树：

• 我们可以找到一个度数为三的节点，树在这里产生了分叉。显然这个节点到根的路径上的所有节点都是随便填的。

• 两个叶子节点肯定是一个 1 一个 2。从下往上填，填 1 的叶子节点上面必须填 2，这样这个子树和是 3，所以填 2 的叶子节点上面必须填 2，以此类推。你会发现在有一边到达度数为三的节点之前，只能填 2。

• 然后讨论是填 1 的叶子节点浅还是填 2 的叶子节点浅。

  • 如果一样深剩下的随便填。

  • 如果填 1 的叶子节点浅，剩下的也是随便填。

  • 如果填 2 的叶子节点浅，考虑填 1 的叶子节点到根的路径上，从下往上第一个目前还没被填的节点。这个节点只能填 2。剩下就随便填了。

这样这个题就做完了。

首先判断叶子节点个数，大于 2 直接输出 0，等于 1 直接输出 O(2^n)。否则，找度数为三的节点和两个叶子节点的深度。然后按照上面做就行了。

submission

:::success[代码如下]

#include<iostream>
#include<vector>
using namespace std;
const int mod = 1e9+7;
int t;
int n, mxdep;
long long pw[200010];
int dep[200010];
vector<int> g[200010];
void dfs(int u, int fa) {
    dep[u] = dep[fa] + 1;
    //mxdep = max(mxdep, dep[u]);
    for(auto v : g[u]) {
        if(v == fa) continue;
        dfs(v, u);
    }
}
void solve() {
    cin >> n; //mxdep = 0;
    for(int i = 1; i <= n; i ++) g[i].clear();
    for(int i = 1; i < n; i ++) {
        int u, v; cin >> u >> v;
        g[u].push_back(v); g[v].push_back(u);
    }
    int cnt = 0; int id1 = 0, id2 = 0;
    for(int i = 2; i <= n; i ++)
        if(g[i].size() == 1) {
            cnt ++;
            if(!id1) id1 = i;
            else if(!id2) id2 = i;
        }
    if(cnt > 2) {
        cout << 0 << '\n';
        return;
    }
    if(cnt == 1) {
        cout << pw[n] << '\n';
        return;
    }
    dfs(1, 0);
    int id = 0;
    for(int i = 1; i <= n; i ++) if(g[i].size() == 3) id = i;
    if(g[1].size() == 2) id = 1;
    int mn = min(dep[id1] - dep[id], dep[id2] - dep[id]);
    //cout << mn << '\n';
    if(dep[id1] - dep[id] == dep[id2] - dep[id]) cout << pw[n - 2 * mn + 1] <<'\n';
    else cout << (pw[n - 2 * mn] + pw[n - 2 * mn - 1]) % mod << '\n';
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin >> t;
    pw[0] = 1;
    for(int i = 1; i <= 2e5; i ++) pw[i] = pw[i - 1] * 2 % mod;
    while(t --) solve();
    return 0;
}

:::