Description
小机房有棵焕狗种的树，树上有N个节点，节点标号为0到N-1，有两只虫子名叫飘狗和大吉狗，分居在两个不同的节点上。有一天，他们想爬到一个节点上去搞基，但是作为两只虫子，他们不想花费太多精力。
已知从某个节点爬到其父亲节点要花费 c 的能量（从父亲节点爬到此节点也相同），他们想找出一条花费精力最短的路，以使得搞基的时候精力旺盛，他们找到你要你设计一个程序来找到这条路，要求你告诉他们最少需要花费多少精力
Input
第一行一个n，接下来n-1行每一行有三个整数u，v, c 。表示节点 u 爬到节点 v 需要花费 c 的精力。
第n+1行有一个整数m表示有m次询问。接下来m行每一行有两个整数 u ，v 表示两只虫子所在的节点
Output
一共有m行，每一行一个整数，表示对于该次询问所得出的最短距离。
Sample Input
3
1 0 1
2 0 1
3
1 0
2 0
1 2
Sample Output
1
1
2
HINT
1<=n<=50000， 1<=m<=75000， 0<=c<=1000
Source
Solution
倍增求LCA, $O((n + m)logn)$
#include <bits/stdc++.h>
using namespace std;
struct edge
{
int v, w, nxt;
}e[];
int fst[], q[], front, back;
int fa[][], dis[], dep[]; void addedge(int i, int u, int v, int w)
{
e[i] = (edge){v, w, fst[u]}, fst[u] = i;
} int LCA(int u, int v)
{
if(dep[u] > dep[v]) swap(u, v);
for(int i = ; ~i; i--)
if(dep[fa[i][v]] >= dep[u])
v = fa[i][v];
if(u == v) return u;
for(int i = ; ~i; i--)
if(fa[i][u] != fa[i][v])
u = fa[i][u], v = fa[i][v];
return fa[][u];
} int main()
{
int n, m, u, v, w;
cin >> n;
for(int i = ; i < n; i++)
{
cin >> u >> v >> w;
addedge(i << , ++u, ++v, w);
addedge(i << | , v, u, w);
}
q[++back] = , dep[] = fa[][] = ;
while(front != back)
{
u = q[++front];
for(int i = fst[u]; i; i = e[i].nxt)
if(e[i].v != fa[][u])
{
q[++back] = e[i].v;
dep[e[i].v] = dep[u] + ;
fa[][e[i].v] = u;
dis[e[i].v] = dis[u] + e[i].w;
}
}
for(int i = ; i <= ; i++)
for(int j = ; j <= n; j++)
fa[i][j] = fa[i - ][fa[i - ][j]];
cin >> m;
while(m--)
{
cin >> u >> v, u++, v++;
cout << dis[u] + dis[v] - * dis[LCA(u, v)] << endl;
}
return ;
}
Tarjan求LCA, $O(n + m)$（写法较鬼畜）
#include <bits/stdc++.h>
using namespace std;
struct edge
{
int v, w, nxt;
}e[];
struct query
{
int u, v, nxt;
}q[];
int efst[], qfst[], fa[], lca[], dis[];
bool vis[]; void addedge(int i, int u, int v, int w)
{
e[i] = (edge){v, w, efst[u]}, efst[u] = i;
} void addquery(int i, int u, int v)
{
q[i] = (query){u, v, qfst[u]}, qfst[u] = i;
} int get_dis(int i)
{
return dis[q[i << ].u] + dis[q[i << ].v] - * dis[lca[i]];
} int getfa(int x)
{
return fa[x] = x == fa[x] ? x : getfa(fa[x]);
} void Tarjan(int u)
{
fa[u] = u, vis[u] = true;
for(int i = efst[u]; i; i = e[i].nxt)
if(!vis[e[i].v])
{
dis[e[i].v] = dis[u] + e[i].w;
Tarjan(e[i].v);
fa[e[i].v] = u;
}
for(int i = qfst[u]; i; i = q[i].nxt)
{
int v = q[i].u == u ? q[i].v : q[i].u;
if(vis[v]) lca[i >> ] = getfa(fa[v]);
}
} int main()
{
int n, m, u, v, w;
cin >> n;
for(int i = ; i < n; i++)
{
cin >> u >> v >> w;
addedge(i << , ++u, ++v, w);
addedge(i << | , v, u, w);
}
cin >> m;
for(int i = ; i <= m; i++)
{
cin >> u >> v;
addquery(i << , ++u, ++v);
addquery(i << | , v, u);
}
Tarjan();
for(int i = ; i <= m; i++)
cout << get_dis(i) << endl;
return ;
}
树链剖分求LCA, $O(mlogn)$，我习惯把树剖维护的7个信息写到结构体里。
#include <bits/stdc++.h>
using namespace std;
struct edge
{
int v, w, nxt;
}e[];
struct point
{
int fa, siz, son, dep, dis, dfn, top;
}p[];
int ptot, fst[]; void addedge(int i, int u, int v, int w)
{
e[i] = (edge){v, w, fst[u]}, fst[u] = i;
} void DFS1(int u)
{
p[u].siz = ;
for(int i = fst[u]; i; i = e[i].nxt)
if(e[i].v != p[u].fa)
{
p[e[i].v].fa = u;
p[e[i].v].dep = p[u].dep + ;
p[e[i].v].dis = p[u].dis + e[i].w;
DFS1(e[i].v);
p[u].siz += p[e[i].v].siz;
if(p[e[i].v].siz > p[p[u].son].siz)
p[u].son = e[i].v;
}
} void DFS2(int u, int top)
{
p[u].dfn = ++ptot, p[u].top = top;
if(p[u].son) DFS2(p[u].son, top);
for(int i = fst[u]; i; i = e[i].nxt)
if(e[i].v != p[u].fa && e[i].v != p[u].son)
DFS2(e[i].v, e[i].v);
} int LCA(int u, int v)
{
while(p[u].top != p[v].top)
{
if(p[p[u].top].dep > p[p[v].top].dep) swap(u, v);
v = p[p[v].top].fa;
}
if(p[u].dep > p[v].dep) swap(u, v);
return u;
} int main()
{
int n, m, u, v, w;
cin >> n;
for(int i = ; i < n; i++)
{
cin >> u >> v >> w;
addedge(i << , ++u, ++v, w);
addedge(i << | , v, u, w);
}
p[].dep = , DFS1(), DFS2(, );
cin >> m;
while(m--)
{
cin >> u >> v, u++, v++;
cout << p[u].dis + p[v].dis - * p[LCA(u, v)].dis << endl;
}
return ;
}
LCT, $O(mlog^{2}n)$
#include <bits/stdc++.h>
using namespace std;
struct LCT
{
int fa, c[], rev, key, sum;
int& operator [] (int i)
{
return c[i];
}
}a[];
int sta[], top; void push_up(int k)
{
a[k].sum = a[a[k][]].sum + a[a[k][]].sum + a[k].key;
} void push_down(int k)
{
if(a[k].rev)
{
a[a[k][]].rev ^= , a[a[k][]].rev ^= ;
swap(a[k][], a[k][]), a[k].rev = ;
}
} bool isroot(int x)
{
return a[a[x].fa][] != x && a[a[x].fa][] != x;
} void rotate(int x)
{
int y = a[x].fa, z = a[y].fa;
int dy = a[y][] == x, dz = a[z][] == y;
if(!isroot(y)) a[z][dz] = x;
a[y][dy] = a[x][dy ^ ], a[a[x][dy ^ ]].fa = y;
a[x][dy ^ ] = y, a[y].fa = x, a[x].fa = z;
push_up(y);
} void splay(int x)
{
sta[top = ] = x;
for(int i = x; !isroot(i); i = a[i].fa)
sta[++top] = a[i].fa;
while(top)
push_down(sta[top--]);
while(!isroot(x))
{
int y = a[x].fa, z = a[y].fa;
if(!isroot(y))
if(a[y][] == x ^ a[z][] == y) rotate(x);
else rotate(y);
rotate(x);
}
push_up(x);
} void access(int x)
{
for(int i = ; x; x = a[x].fa)
splay(x), a[x][] = i, i = x;
} void make_root(int x)
{
access(x), splay(x), a[x].rev ^= ;
} void link(int x, int y)
{
make_root(x), a[x].fa = y;
} void cut(int x, int y)
{
make_root(x), access(y), splay(y), a[y][] = a[x].fa = ;
} int find_root(int x)
{
access(x), splay(x);
while(a[x][])
x = a[x][];
return x;
} int main()
{
int n, m, u, v, w;
cin >> n;
for(int i = ; i < n; i++)
{
cin >> u >> v >> w;
a[i + n].sum = a[i + n].key = w;
link(++u, i + n), link(i + n, ++v);
}
cin >> m;
while(m--)
{
cin >> u >> v;
make_root(++u), access(++v), splay(v);
printf("%d\n", a[v].sum);
}
return ;
}