lca +差分 老是wa 有大哥帮忙砍下嘛。
查看原帖
lca +差分 老是wa 有大哥帮忙砍下嘛。
701787
euyia楼主2022/12/17 17:03

#include <bits/stdc++.h>
using namespace std;
#define ios ios::sync_with_stdio(0)
#define endl '\n'
#define int long long
#define ar array<int, 2>
#define arr array<int, 3>
const int N = 234567, M = 2 * N;
const int inf = 0x3f3f3f3f;
int mod = 998244353; //1e9+7;
int t, n, m, k;
int l, h[N], ne[M], eg[N], e[M], f[N][22], d[N];
void add(int u, int v, int i)
{
    e[++l] = v, ne[l] = h[u], eg[l] = i, h[u] = l;
};
void bfs()
{
    d[1] = 1;
    queue<int> q;
    q.push(1);
    while (q.size())
    {
        int u = q.front();
        q.pop();
        for (int i = h[u]; i; i = ne[i])
        {
            int v = e[i];
            if (d[v])
                continue;
            d[v] = d[u] + 1;
            f[v][0] = u;
            q.push(v);
            for (int j = 1; j <= k; ++j)
                f[v][j] = f[f[v][j - 1]][j - 1];
        }
    }
};
int lca(int x, int y)
{
    if (d[x] < d[y])
        swap(x, y);
    int tmp = d[y] - d[x];
    for (int i = k; ~i; i--)
        if (tmp & (1 << i))
            x = f[x][i];
    if (x == y)
        return x;
    for (int i = k; ~i; i--)
        if (f[x][i] != f[y][i])
            x = f[x][i], y = f[y][i];
    return f[x][0];
};
int ans[N], cnt[N];
void dfs(int u, int p)
{
    for (int i = h[u]; i; i = ne[i])
    {
        int v = e[i];
        if (v == p)
            continue;
        dfs(v, u);
        cnt[u] += cnt[v];
        ans[eg[i]] = cnt[v];
    }
};
signed main()
{
    ios;
#ifdef DEBUG
    freopen("../1.in", "r", stdin);
#endif
    cin >> n;
    for (int i = 1; i < n; ++i)
    {
        int x, y;
        cin >> x >> y;
        add(x, y, i), add(y, x, i);
    }
    k = 20;
    bfs();
    cin >> m;
    while (m--)
    {
        int x, y;
        cin >> x >> y;
        cnt[x]++, cnt[y]++;
        cnt[lca(x, y)] -= 2;
    }
    dfs(1, 0);
    for (int i = 1; i < n; ++i)
        cout << ans[i] << " ";
};
2022/12/17 17:03
加载中...