codevs 2370 小机房的树(LCA)

过了这么长的时间终于开始看LCA了...

有一次训练题卡在LCA当时不会...拖了好久好久...其实现在还是不会...

只会tarjan...

传送门

板子题咯

tarjan的算法就是基于先序遍历的顺序的

#include <bits/stdc++.h>
using namespace std; inline int read() {
int x = , f = ; char ch = getchar();
while (ch < '' || ch > '') { if (ch == '-') f = -; ch = getchar(); }
while (ch >= '' && ch <= '') { x = x * + ch - ''; ch = getchar(); }
return x * f;
} const int maxn = 5e5 + ;
//const int maxm = 8e4 + 10; struct Edge { int to, next, c; } edge[ * maxn];
int cnt, head[maxn];
struct Qedge { int to, next; } qedge[ * 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] = ;
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 % ) lca[i + ] = lca[i];
else lca[i-] = lca[i];
}
}
} int main() {
n = read();
for (int i = ; i < n - ; i++) {
int u = read(), v =read(), c = read();
addedge(u, v, c);
addedge(v, u, c);
}
m = read();
for (int i = ; i < m; i++) {
int u = read(), v = read();
addqedge(u, v);
addqedge(v, u);
}
dfs();
for (int i = ; i <= m; i++) {
int ans = dep[qedge[ * i].to] - * dep[lca[ * i]] + dep[qedge[ * i - ].to];
printf("%d\n", ans);
}
return ;
}
上一篇:Codevs 2370 小机房的树 LCA 树上倍增


下一篇:jquery商城购物车右侧悬浮加入购物车动画效果