12746번: Traffic (Large)

https://www.acmicpc.net/problem/12746


$O((n+q)\lg n)$

주어진 그래프를 rooted tree 로 만든다.
(x,y) 쿼리가 들어오면 s[x]++, s[y]++, s[lca(x,y)]-=2를 해주고
루트를 시작점으로 dfs를 돌면서 자식의 s[]를 부모의 s[]에 누적시키면 모든 간선의 방문 수를 알 수 있다.
lca 쿼리를 O(lgn)이 되도록 구현해야 한다.

#include<cstdio>
#include<vector>
using namespace std;
const int MXN = 222222;
int n, q, dp[MXN + 1][18], dep[MXN + 1], s[MXN + 1], r;
vector<int> adj[MXN + 1];
pair<int, int> t;
void f(int x) {
    for (auto it : adj[x]) {
        if (it == dp[x][0]) continue;
        dep[it] = dep[x] + 1;
        dp[it][0] = x;
        for (int i = 1; i<18; i++) dp[it][i] = dp[dp[it][i - 1]][i - 1];
        f(it);
    }
}
void g(int x) {
    for (auto it : adj[x]) if (it^dp[x][0]) {
        g(it);
        pair<int, int> tp = { x,it };
        if (x>it) swap(tp.first, tp.second);
        if (s[it]>r || s[it] == r&&tp<t) {
            r = s[it];
            t = tp;
        }
        s[x] += s[it];
    }
}
int lca(int x, int y) {
    if (dep[x]<dep[y]) swap(x, y);
    for (int i = 17; i >= 0; i--)
        if (dep[x] - dep[y] >= 1 << i) x = dp[x][i];
    if (x == y) return x;
    for (int i = 17; i >= 0; i--)
        if (dp[x][i] ^ dp[y][i]) x = dp[x][i], y = dp[y][i];
    return dp[x][0];
}
int main() {
    scanf("%d%d", &n, &q);
    for (int i = 1, x, y; i<n; i++) {
        scanf("%d%d", &x, &y);
        adj[x].push_back(y);
        adj[y].push_back(x);
    }
    f(1);
    while (q--) {
        int x, y;
        scanf("%d%d", &x, &y);
        s[x]++;
        s[y]++;
        s[lca(x, y)] -= 2;
    }
    g(1);
    printf("%d %d %d", t.first, t.second, r);
    return 0;
}