过了这么长的时间终于开始看 LCA 了...
有一次训练题卡在 LCA 当时不会... 拖了好久好久... 其实现在还是不会...
只会 tarjan...
传送门 http://codevs.cn/problem/2370/
板子题咯
tarjan 的算法就是基于先序遍历的顺序的
- #include <bits/stdc++.h>
- using namespace std;
- inline int read() {
- int x = 0, f = 1; char ch = getchar();
- while (ch <'0' || ch> '9') { if (ch == '-') f = -1; ch = getchar(); }
- while (ch>= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
- return x * f;
- }
- const int maxn = 5e5 + 10;
- //const int maxm = 8e4 + 10;
- struct Edge { int to, next, c; } edge[2 * maxn];
- int cnt, head[maxn];
- struct Qedge { int to, next; } qedge[2 * maxn];
- int qcnt, qhead[maxn], n, m;
- int lca[maxn], dep[maxn], par[maxn];
- bool vis[maxn];
- inline void addedge(int u, int v, int c) {
- edge[++cnt].to = v;
- edge[cnt].c = c;
- edge[cnt].next = head[u];
- head[u] = cnt;
- }
- inline void addqedge(int u, int v) {
- qedge[++qcnt].to = v;
- qedge[qcnt].next = qhead[u];
- qhead[u] = qcnt;
- }
- int getfa(int x) { return x == par[x] ? x : par[x] = getfa(par[x]); }
- void dfs(int u) {
- par[u] = u;
- vis[u] = 1;
- for (int i = head[u]; i; i = edge[i].next) {
- int v = edge[i].to;
- if (!vis[v]) {
- dep[v] = dep[u] + edge[i].c;
- dfs(v);
- par[v] = u;
- }
- }
- for (int i = qhead[u]; i; i = qedge[i].next) {
- int v = qedge[i].to;
- if (vis[v]) {
- lca[i] = getfa(v);
- if (i % 2) lca[i + 1] = lca[i];
- else lca[i-1] = lca[i];
- }
- }
- }
- int main() {
- n = read();
- for (int i = 0; i < n - 1; i++) {
- int u = read(), v =read(), c = read();
- addedge(u, v, c);
- addedge(v, u, c);
- }
- m = read();
- for (int i = 0; i < m; i++) {
- int u = read(), v = read();
- addqedge(u, v);
- addqedge(v, u);
- }
- dfs(0);
- for (int i = 1; i <= m; i++) {
- int ans = dep[qedge[2 * i].to] - 2 * dep[lca[2 * i]] + dep[qedge[2 * i - 1].to];
- printf("%d\n", ans);
- }
- return 0;
- }
- View Code
来源: http://www.bubuko.com/infodetail-3037244.html