LCA系列 hdu2587

Posted by Cww97 on 2016-11-10

版权声明:本文为博主原创文章,未经博主允许不得转载。原文所在http://blog.csdn.net/cww97 https://blog.csdn.net/cww97/article/details/53121432
http://acm.hdu.edu.cn/showproblem.php?pid=2586

好久不写LCA了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
typedef long long LL;
const int N = 1e5+10;
struct tree
{
struct Edge{
int from,to,cost;
Edge(){}
Edge(int x,int y,int z):from(x),to(y),cost(z){}
}edges[N];
int E,head[N],Next[N],dep[N],fa[N][20];
LL di[N][20];
bool vis[N];

inline void Init()
{
E = 0;
memset(head,-1,sizeof(head));
memset(Next,-1,sizeof(Next));
memset( vis, 0,sizeof( vis));
}

inline void link(int x,int y,int z)
{
edges[++E] = Edge(x,y,z);
Next[E] = head[x];
head[x] = E;
}

void dfs(int x)
{
vis[x] = 1;
for (int i=1;i<17;i++)if (dep[x]>= 1<<i){
fa[x][i] = fa[fa[x][i-1]][i-1];
di[x][i] = di[x][i-1] + di[fa[x][i-1]][i-1];
}
for (int i=head[x];i!=-1;i=Next[i]){
Edge e = edges[i];
if (vis[e.to])continue;
dep[e.to] = dep[x] + 1;
fa[e.to][0] = x;
di[e.to][0] = e.cost;
dfs(e.to);
}
}

inline int lca(int x,int y)
{
if (dep[x]<dep[y])swap(x,y);
int t = dep[x] - dep[y];
for (int i=0;i<=16;i++)
if (t&(1<<i)) x = fa[x][i];
for (int i=16;i>=0;i--)
if (fa[x][i]!=fa[y][i]){
x = fa[x][i]; y = fa[y][i];
}
if (x == y) return x;
return fa[x][0];
}

inline LL ask(int x,int f)
{
int t = dep[x] - dep[f];
LL ans = 0;
for (int i=0;i<17;i++)if (t&(1<<i)){
ans += di[x][i];
x = fa[x][i];
}
return ans;
}
} g ;

int main()
{
int T,n,m,x,y,z;
scanf("%d",&T);
for (;T--;){
scanf("%d%d",&n,&m);
g.Init();
for (int i=1;i<n;i++){
scanf("%d%d%d",&x,&y,&z);
g.link(x,y,z);
g.link(y,x,z);
}
g.dep[1] = 0;
g.dfs(1);
for (;m--;){
scanf("%d%d",&x,&y);
int f = g.lca(x,y);
LL ans = g.ask(x,f) + g.ask(y,f);
printf("%I64d\n",ans);
}
}
return 0;
}

马住,慢慢填
http://www.cnblogs.com/scau20110726/archive/2013/06/14/3135095.html