Untitled

 avatardomovonok
c_cpp
a month ago
1.9 kB
2
Indexable
Never
#include "bits/stdc++.h"
using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(x...)
#endif

constexpr int maxN = 1e5;
constexpr int LOG = 17;

vector<int> graph[maxN], tin(maxN), tout(maxN);
vector<vector<int>> up(maxN, vector<int> (LOG + 1));
int timer = 1;

void dfs(int u, int p) {
    tin[u] = timer++;
    up[u][0] = p;
    for (int i = 1; i <= LOG; i++) {
        up[u][i] = up[up[u][i - 1]][i - 1];
    }
    for (int &g : graph[u]) {
        if (g != p) {
            dfs(g, u);
        }
    }
    tout[u] = timer++;
}

bool isParent(int u, int v) {
    return tin[u] < tin[v] && tout[u] > tout[v];
}

int lca(int u, int v) {
    if (isParent(u, v)) return u;
    if (isParent(v, u)) return v;
    for (int p = LOG; p >= 0; p--) {
        if (!isParent(up[u][p], v)) {
            u = up[u][p];
        }
    }
    return up[u][0];
}

map<pair<int, int>, int> edges; 
vector<int> value(maxN), ans(maxN - 1);

void calc(int u, int curv, int p) {
    curv += value[u];
    for (int &g : graph[u]) {
        if (g != p) {
            ans[edges[{u, g}]] = curv;
            calc(g, curv, u);
        }
    }
}

void solve() {
    int n;
    cin >> n;
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        u--; v--;
        graph[u].push_back(v);
        graph[v].push_back(u);
        edges[{u, v}] = i;
        edges[{v, u}] = i;
    }
    dfs(0, 0);
    int k;
    cin >> k;
    while (k--) {
        int a, b;
        cin >> a >> b;
        a--; b--;
        value[a]--;
        value[b]--;
        value[lca(a, b)]++;
    }
    calc(0, 0, 0);
    for (int i = 0; i < n - 1; i++) {
        cout << ans[i] << ' ';
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int tests = 1;
    // cin >> tests;
    while (tests--) {
        solve();
    }
    return 0;
}