t求调
查看原帖
t求调
637788
kimi0705楼主2023/8/28 17:55
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5 + 10;
const int M = 20;
int n, m;
int fa[N][M], deep[N], cnt[N]; // fa[i][j] i 的上 2 ^ j 代祖宗节点、deep 深度、cnt 差分。
int V[N], U[N];
vector<int> Edge[N];
int x[N], y[N];
void dfs(int x, int Fa) { // 求父亲节点。
    fa[x][0] = Fa, deep[x] = deep[Fa] + 1; // 根节点深度为 1。
    for (int i = 1; i <= log2(deep[x]); i++) fa[x][i] = fa[fa[x][i - 1]][i - 1];
    for (int i : Edge[x]) {
        if (i != Fa) {
            dfs(i, x);
        }
    }
}
int lca(int x, int y) {
    if (deep[x] < deep[y]) {
        swap(x, y);
    }
    while (deep[x] > deep[y]) {
        x = fa[x][(int)(log2(deep[x] - deep[y] + 1) - 1)];
    }
    if (x == y) {
        return x;
    }
    for (int i = log2(deep[x]) - 1; i >= 0; i--) {
        if (fa[x][i] != fa[y][i]) {
            x = fa[x][i];
            y = fa[y][i];
        }
    }
    return fa[x][0];
}
void get_ans(int x, int fa = 1) {
    for (int son : Edge[x]) {
        if (son == fa) {
            continue;
        }
        get_ans(son, x);
        cnt[x] += cnt[son];
    }
}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n;
    for (int i = 1; i < n; i++) {
        cin >> V[i] >> U[i];
        Edge[V[i]].push_back(U[i]);
        Edge[U[i]].push_back(V[i]);
    }
    cin >> m;
    for (int i = 1; i <= m; i++) cin >> x[i] >> y[i];
    dfs(1, 1);
    // for (int i = 1; i <= n; i++) cout << fa[i] << ' ';
    for (int i = 1; i <= m; i++) {
        int Lca = lca(x[i], y[i]); // 计算lca
        cnt[x[i]]++, cnt[y[i]]++, cnt[Lca] -= 2;
    }
    get_ans(1);
    for (int i = 1; i < n; i++) {
        if (deep[U[i]] > deep[V[i]]) {
            cout << cnt[U[i]] << ' ';
        } else {
            cout << cnt[V[i]] << ' ';
        }
    }
    return 0;
}
2023/8/28 17:55
加载中...