12745번: Traffic (Small)

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


dfs를 q번 돌게 했더니 시간 초과되었다.
같은 시간 복잡도에서도 상수가 작은 lca 연산으로 해결한다.

$O(nq)$

주어진 그래프를 rooted tree 로 만든다.
(x,y) 쿼리가 들어오면 x와 y를 연결하는 경로상의 간선에 카운트 해준다.

#include<cstdio>
#include<vector>
using namespace std;
const int MXN = 2222;
int n, q, s[MXN + 1], par[MXN + 1], dep[MXN + 1], r;
vector<int> adj[MXN + 1];
pair<int, int> t;
void f(int x) {
    for (auto it : adj[x]) if (it^par[x]) {
        par[it] = x;
        dep[it] = dep[x] + 1;
        f(it);
    }
}
void g(int x, int y) {
    s[x]++;
    pair<int, int> tp = { x,y };
    if (tp.first>tp.second) swap(tp.first, tp.second);
    if (s[x]>r || s[x] == r&&tp<t) {
        r = s[x];
        t = tp;
    }
}
void lca(int x, int y) {
    if (dep[x]<dep[y]) swap(x, y);
    while (dep[x]>dep[y]) g(x, par[x]), x = par[x];
    while (par[x] ^ par[y]) {
        g(x, par[x]);
        g(y, par[y]);
        x = par[x];
        y = par[y];
    }
    if (x^y) g(x, par[x]), g(y, par[y]);
}
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);
        lca(x, y);
    }
    printf("%d %d %d", t.first, t.second, r);
    return 0;
}