题解：求树上最短路，所以直接LCA：
倍增求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 |
#include <cstdio>int f[10010][18];int s[10010],d[10010],from[10010];int g[10010],nxt[20010],edv[20010],edw[20010],cnt;bool
vis[10010];int q,a,b,e,n,m,i,j,x,y,tmp;void
swap(int
&a,int
&b){int
c=a;a=b;b=c;}void
add(int
u,int v,int w){ edv[++cnt]=v;edw[cnt]=w; nxt[cnt]=g[u];g[u]=cnt;}void
dfs(int
x,int fa,int
fr,int
sum){ from[x]=fr;f[x][0]=fa; vis[x]=1; d[x]=d[fa]+1; s[x]=sum; for(int
i=g[x];i;i=nxt[i])if(!vis[edv[i]])dfs(edv[i],x,fr,sum+edw[i]);}int
lca(int
x,int y){ if(x==y)return
x; if(d[x]<d[y])swap(x,y); for(int
i=17;i>=0;i--)if(d[f[x][i]]>=d[y])x=f[x][i]; if(x==y)return
x; for(int
i=17;i>=0;i--)if(f[x][i]!=f[y][i])x=f[x][i],y=f[y][i]; return
f[x][0];}int
main(){ while(~scanf("%d%d%d",&n,&m,&q)){ for(i=0;i<=10000;i++) for(j=0;j<18;j++) f[i][j]=0; for(i=0;i<=n;i++)vis[i]=from[i]=s[i]=d[i]=g[i]=0; cnt=0; for(i=0;i<m;i++){ scanf("%d%d%d",&a,&b,&e); add(a,b,e);add(b,a,e); } for(i=1;i<=n;i++)if(!vis[i])dfs(i,0,i,0); for(j=1;j<18;j++) for(i=1;i<=n;i++)f[i][j]=f[f[i][j-1]][j-1]; for(i=0;i<q;i++){ scanf("%d%d",&x,&y); if(from[x]!=from[y])puts("Not connected"); else
printf("%d\n",s[x]+s[y]-2*s[lca(x,y)]); } } return
0;} |
动态树：
|
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 |
#include <cstdio>#include <cstring>#define N 20010using
namespace std;int f[N],son[N][2],sum[N],data[N],a[N];bool
rev[N];inline
void swap(int&a,int&b){int
c=a;a=b;b=c;}inline
bool isroot(int
x){return
!f[x]||son[f[x]][0]!=x&&son[f[x]][1]!=x;}inline
void pb(int
x){ if(rev[x]){ swap(son[x][0],son[x][1]); rev[son[x][0]]^=1;rev[son[x][1]]^=1; rev[x]=0; }}inline
void up(int
x){ sum[x]=data[x]+sum[son[x][0]]+sum[son[x][1]];}inline
void rotate(int
x){ int
y=f[x];int
w=(son[y][1]==x); son[y][w]=son[x][w^1]; if(son[x][w^1])f[son[x][w^1]]=y; if(f[y]){ int
z=f[y]; if(son[z][0]==y)son[z][0]=x; if(son[z][1]==y)son[z][1]=x; } f[x]=f[y];son[x][w^1]=y;f[y]=x;up(y);}inline
void splay(int
x){ int
s=1,i=x,y;a[1]=i; while(!isroot(i))a[++s]=i=f[i]; while(s)pb(a[s--]); while(!isroot(x)){ y=f[x]; if(!isroot(y)){if((son[f[y]][0]==y)^(son[y][0]==x))rotate(x);else
rotate(y);} rotate(x); } up(x);}inline
void access(int
x){ for(int
y=0;x;y=x,x=f[x]){ splay(x); son[x][1]=y; up(x); }}inline
int root(int
x){ access(x); splay(x); while(son[x][0])x=son[x][0]; return
x;}inline
void makeroot(int
x){ access(x); splay(x); rev[x]^=1;}inline
void link(int
x,int y){ makeroot(x); f[x]=y; access(x);}inline
int getsum(int
x,int y){ makeroot(x); access(y); splay(x); return
sum[x];}inline
void read(int&a){ char
ch;while(!((ch=getchar())>=‘0‘)&&(ch<=‘9‘)); a=ch-‘0‘;while(((ch=getchar())>=‘0‘)&&(ch<=‘9‘))a*=10,a+=ch-‘0‘;}int
n,m,x,y,c,q;inline
void solve(){ memset(f,0,sizeof
f); memset(son,0,sizeof
son); memset(sum,0,sizeof
sum); memset(data,0,sizeof
data); memset(rev,0,sizeof
rev); read(m);read(q); for(int
i=1;i<=m;i++){ read(x);read(y);read(c); sum[n+i]=data[n+i]=c; link(x,n+i);link(n+i,y); } while(q--){ read(x);read(y); if(root(x)!=root(y))puts("Not connected"); else
printf("%d\n",getsum(x,y)); }}int
main(){ while(~scanf("%d",&n))solve(); return
0;} |
HDU 2874 Connections between cities,布布扣,bubuko.com
HDU 2874 Connections between cities
原文：http://www.cnblogs.com/forever97/p/3576853.html