lca的倍增策略不仅可以维护最近公共祖先，还可以维护其他具有区间可维护性的信息，例如本题中维护的最小限重。
本题调了好久，最后发现原因是数组用混了。以后一定要记准各个数组含义，千万不要混啊。。。
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<algorithm>
5 #include<vector>
6
7 using namespace std;
8
9 const int Maxn = 1e5+10,Maxm = 5e5+10;
10
11 struct Edge{
12 int fr,to,wi;
13 bool operator <(const Edge& x)const{
14 return wi > x.wi;
15 }
16 }edges[Maxm],e;
17
18 struct node{int to,wi;};
19
20 int n,m,x,y,z,cnte,q;
21 vector<node> g[Maxn];
22
23 int read(){
24 int ans = 0;char last = ' ',ch = getchar();
25 while(ch < '0'||ch > '9')last = ch,ch = getchar();
26 while('0' <= ch&&ch <= '9')ans = ans*10+ch-'0',ch = getchar();
27 if(last == '-')return -ans;return ans;
28 }
29
30 int fa[Maxn];
31 int find(int x){
32 if(fa[x] == x)return x;
33 return fa[x] = find(fa[x]);
34 }
35
36 void kruscal(){
37 sort(edges+1,edges+m+1);
38 for(int i = 1;i <= n;i++)fa[i] = i;
39 for(int i = 1;i <= m;i++){
40 e = edges[i];
41 if(find(e.fr) != find(e.to)){
42 fa[fa[e.fr]] = fa[e.to];
43 g[e.fr].push_back((node){e.to,e.wi});
44 g[e.to].push_back((node){e.fr,e.wi});
45 }
46 }
47 }
48
49 int jump[Maxn][20],wide[Maxn][20];
50 int dep[Maxn];
51
52 void workdep(int rt,int fa){
53 dep[rt] = dep[fa]+1;
54 for(int i = 0;i < g[rt].size();i++){
55 int to = g[rt][i].to,wi = g[rt][i].wi;
56 if(to == fa)continue;
57 jump[to][0] = rt;
58 wide[to][0] = wi;
59 workdep(to,rt);
60 }
61 }
62
63 void initall(){
64 for(int i = 1;i <= 18;i++)
65 for(int j = 1;j <= n;j++){
66 jump[j][i] = jump[jump[j][i-1]][i-1];
67 wide[j][i] = min(wide[j][i-1],wide[jump[j][i-1]][i-1]);
68 }
69 }
70
71 int ask(int x,int y){
72 int ans = 1<<30;
73 if(find(x) != find(y))return -1;
74 int dx = dep[x],dy = dep[y];
75 if(dx < dy)swap(x,y),swap(dx,dy);//printf("start::%d,%d:%d\n",x,y,ans);
76 for(int i = 18;i >= 0;i--)if(dep[jump[x][i]] > dy){
77 ans = min(ans,wide[x][i]);
78 x = jump[x][i];//printf("->%d,%d:%d\n",x,y,ans);
79 }
80 if(dx != dy){
81 ans = min(ans,wide[x][0]);//printf("->%d,%d:%d\n",x,y,ans);
82 if((x=jump[x][0]) == y)return ans;//printf("->%d,%d:%d\n",x,y,ans);
83 }
84 for(int i = 18;i >= 0;i--)if(jump[x][i] != jump[y][i]){
85 ans = min(ans,min(wide[x][i],wide[y][i]));
86 x = jump[x][i],y = jump[y][i];//printf("->%d,%d:%d\n",x,y,ans);
87 }
88 // cout << "ans::";
89 return min(ans,min(wide[x][0],wide[y][0]));
90 }
91
92 int main(){
93 n = read(),m = read();
94 for(int i = 1;i <= m;i++)edges[i] = (Edge){read(),read(),read()};
95 q = read();
96 kruscal();
97 memset(wide,0x3f,sizeof(wide));
98 for(int i = 1;i <= n;i++)if(!dep[i])workdep(i,0);
99 // cout << "dep[]: ";for(int i = 1;i <= n;i++)cout << dep[i] << ' ';cout << endl;
100 initall();
101
102 /* for(int i = 0;i <= 18;i++){
103 for(int j = 1;j <= n;j++)printf("%d ",jump[j][i]);
104 putchar('\n');
105 }
106 putchar('\n');
107 for(int i = 0;i <= 18;i++){
108 for(int j = 1;j <= n;j++)printf("%d ",wide[j][i]);
109 putchar('\n');
110 }
111 putchar('\n');*/
112
113 while(q--)printf("%d\n",ask(read(),read()));
114 return 0;
115 }
调试代码
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<algorithm>
5 #include<vector>
6
7 using namespace std;
8
9 const int Maxn = 1e5+10,Maxm = 5e5+10;
10
11 struct Edge{
12 int fr,to,wi;
13 bool operator <(const Edge& x)const{
14 return wi > x.wi;
15 }
16 }edges[Maxm],e;
17
18 struct node{int to,wi;};
19
20 int n,m,x,y,z,cnte,q;
21 vector<node> g[Maxn];
22
23 int read(){
24 int ans = 0;char last = ' ',ch = getchar();
25 while(ch < '0'||ch > '9')last = ch,ch = getchar();
26 while('0' <= ch&&ch <= '9')ans = ans*10+ch-'0',ch = getchar();
27 if(last == '-')return -ans;return ans;
28 }
29
30 int fa[Maxn];
31 int find(int x){
32 if(fa[x] == x)return x;
33 return fa[x] = find(fa[x]);
34 }
35
36 void kruscal(){
37 sort(edges+1,edges+m+1);
38 for(int i = 1;i <= n;i++)fa[i] = i;
39 for(int i = 1;i <= m;i++){
40 e = edges[i];
41 if(find(e.fr) != find(e.to)){
42 fa[fa[e.fr]] = fa[e.to];
43 g[e.fr].push_back((node){e.to,e.wi});
44 g[e.to].push_back((node){e.fr,e.wi});
45 }
46 }
47 }
48
49 int jump[Maxn][20],wide[Maxn][20];
50 int dep[Maxn];
51
52 void workdep(int rt,int fa){
53 dep[rt] = dep[fa]+1;
54 for(int i = 0;i < g[rt].size();i++){
55 int to = g[rt][i].to,wi = g[rt][i].wi;
56 if(to == fa)continue;
57 jump[to][0] = rt;
58 wide[to][0] = wi;
59 workdep(to,rt);
60 }
61 }
62
63 void initall(){
64 for(int i = 1;i <= 18;i++)
65 for(int j = 1;j <= n;j++){
66 jump[j][i] = jump[jump[j][i-1]][i-1];
67 wide[j][i] = min(wide[j][i-1],wide[jump[j][i-1]][i-1]);
68 }
69 }
70
71 int ask(int x,int y){
72 int ans = 1<<30;
73 if(find(x) != find(y))return -1;
74 int dx = dep[x],dy = dep[y];
75 if(dx < dy)swap(x,y),swap(dx,dy);
76 for(int i = 18;i >= 0;i--)if(dep[jump[x][i]] > dy){
77 ans = min(ans,wide[x][i]);
78 x = jump[x][i];
79 }
80 if(dx != dy){
81 ans = min(ans,wide[x][0]);
82 if((x=jump[x][0]) == y)return ans;
83 }
84 for(int i = 18;i >= 0;i--)if(jump[x][i] != jump[y][i]){
85 ans = min(ans,min(wide[x][i],wide[y][i]));
86 x = jump[x][i],y = jump[y][i];
87 }
88 return min(ans,min(wide[x][0],wide[y][0]));
89 }
90
91 int main(){
92 n = read(),m = read();
93 for(int i = 1;i <= m;i++)edges[i] = (Edge){read(),read(),read()};
94 q = read();
95 kruscal();
96 memset(wide,0x3f,sizeof(wide));
97 for(int i = 1;i <= n;i++)if(!dep[i])workdep(i,0);
98 initall();
99 while(q--)printf("%d\n",ask(read(),read()));
100 return 0;
101 }
Final