题解 | 计树

树形DP思想，计算子节点对父节点的贡献值，即父节点的状态由子节点的状态转移得来。

关于23行计算LCA的解释：

#include <iostream>
#include <vector>

using namespace std;

const int MAXN = 100005;
vector<vector<int>> adj; // 邻接表
bool isInV[MAXN] = {false}; // 统计节点是否属于集合V
long long countV[MAXN] = {0};  // countV[u]统计以u为根的子树中含有V节点的数量
long long LcaCount[MAXN] = {0}; // Final answer cnt[u]

// DFS function to calculate countV and LcaCount
long long dfs(int u, int p) { // 
    long long current_v_num = isInV[u] == true ? 1 : 0;
    long long child_v_size = 0;
    for(auto v: adj[u]){
        if(v != p){ // 只往孩子节点方向遍历，防止往回遍历到父节点
            long long child_v_num = dfs(v, u);
            current_v_num += child_v_num;
            child_v_size += child_v_num*child_v_num;
        }
    }
    LcaCount[u] = current_v_num * current_v_num - child_v_size; // 记录LCA值
    countV[u] = current_v_num;
    return current_v_num;
}

int main() {
    ios_base::sync_with_stdio(false); // Faster I/O
    cin.tie(NULL);
    
    int n, u, v, k;
    cin >> n;
    adj.resize(n + 1);
    for(int i=0; i<n-1; i++){
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    cin >> k;
    for(int i=0; i<k; i++){
        cin >> u;
        isInV[u] = true;
    }
    dfs(1, 0); // 从根节点开始遍历，根节点的父节点设为0
    for(int i=1; i<=n; i++){
        cout << LcaCount[i] << (i==n ? "" : " ");
    }
}