题解

​ 观察可以发现，对于当前节点 $i$ ，从该节点所有子树中选出一些点后构成的节点集合的 LCA 一定是是节点 $i$ 。

这样子可以分成两种情况考虑:

1. 选择节点 $i$

   • 对于每棵子树可以任意选（可以是0）
   • 假设当前子树的节点数为 $cnt$ ，那么可选择的方案数为 $2 ^ {cnt}$ (可以用快速幂，或者预处理都行)
   • 根据乘法原理，当前对答案的贡献为，将所有子树的方案数相乘

2. 不选节点 $i$

   • 不能单独只选一棵子树上的节点 (否则 LCA 就不是 $i$ 了)

   • 所有选择不能是空集 (题目规定)

   • 对于这种情况直接算比较难算我们可以反着算（正难则反）

     当前的方案数可以表示为: 所有子树随便选的方案 - 只选一颗子树的方案(不为空) + 所有子树都不选的方案数(方案数为1)

​ 每次 DFS 时可以返回当前子树的节点数量。

​ 时间复杂度为 $O(n\log n)$

代码

cpp

#include<bits/stdc++.h>

using namespace std;
#define int long long
const int mod = 1e9 + 7;
int qmi(int a, int b){
    int res = 1 % mod;
    while(b)
    {
        if(b & 1) res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}
signed main (){
    ios::sync_with_stdio(false);
    std::cin.tie(0);
    int n; cin >> n;
    vector<vector<int>> g(n + 1);
    for(int i = 0; i < n - 1; i ++)
    {
        int a, b; cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    vector<int> f(n + 1);

    auto dfs = [&](auto dfs, int u, int pre) -> int{
        vector<int> t{1};
        int cnt = 1;
        for(auto i : g[u])
            if(i != pre)
            {
                int ans = dfs(dfs, i, u);
                t.push_back(ans);
                cnt += ans;
            }
        int m = t.size();
        int add = 1, mul = 1;
        for(int i = 1; i < m; i ++)  // 第二种情况不选当前节点
        {
            int kk = qmi(2, t[i]);
            mul = mul * kk % mod;
            add += kk - 1;
            add = (add + mod) % mod;
        }
      	// 选了当前节点的方案数其实就是 mul
        int res = (mul * 2 - add+ mod) % mod;
        res %= mod;
        f[u] = res;
        return cnt;
    };

    dfs(dfs, 1, -1);
    for(int i = 1; i <= n; i ++)
        cout << f[i] << " \n"[i == n];
    return 0;
}

java

# 差分数组
n, m = list(map(int, input().split()))
lefts = list(map(int, input().split()))
rights = list(map(int, input().split()))
Q = int(input())
nums = list(map(int, input().split()))

d = [0] * (n + 2)
for i in range(m):
    left = lefts[i]
    right = rights[i]
    d[left] += 1
    d[right + 1] -= 1

presum = [0]
for x in d:
    presum.append(presum[-1] + x)
for q in nums:
    print(presum[q + 1], end = " ")

题目描述

最近公共祖先简称LCA(Lowest Common Ancestor)两个节点的最近公共祖先，就是这两个点的公共祖先里面离根最远的那个。 小红有一棵有根树，树的根节点为1号节点。定义$f(i)$是:LCA为$i$的非空节点集个数，小红想知道$f(1)$到$f(n)$的值。由于$f(i)$可能很大，因此你需要输出$f(i)$对$10^9+7$取模后的结果

输入描述

第一行输入一个正整数$n$，代表树的节点个数

接下来$n-1$行，每行两个整数$u,v(1\le u,v \le n)$表示树上的边。

$1≤ n ≤ 10^5$

输出描述

输出$n$个整数表示答案

样例

输入

3
1 2
2 3

输出

4 2 1

说明

LCA为1的节点集:(1),(1,2),(1,3),(1,2,3)

LCA为2的节点对:(2),(2,3)

LCA为3的节点对:(3)

输入

5
1 2
1 3
2 4
2 5

输出

23 5 1 1 1