[CodeVS2370] 小机房的树 (LCA, 树链剖分, LCT)

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

1 0 1

2 0 1

1 0

2 0

1 2

Sample Output

HINT

　　1<=n<=50000， 1<=m<=75000， 0<=c<=1000

Source

Solution

　　倍增求LCA, $O((n + m)logn)$

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 struct edge
 4 {
 5     int v, w, nxt;
 6 }e[100005];
 7 int fst[50005], q[50005], front, back;
 8 int fa[17][50005], dis[50005], dep[50005];
 9 
10 void addedge(int i, int u, int v, int w)
11 {
12     e[i] = (edge){v, w, fst[u]}, fst[u] = i;
13 }
14 
15 int LCA(int u, int v)
16 {
17     if(dep[u] > dep[v]) swap(u, v);
18     for(int i = 16; ~i; i--)
19         if(dep[fa[i][v]] >= dep[u])
20             v = fa[i][v];
21     if(u == v) return u;
22     for(int i = 16; ~i; i--)
23         if(fa[i][u] != fa[i][v])
24             u = fa[i][u], v = fa[i][v];
25     return fa[0][u];
26 }
27 
28 int main()
29 {
30     int n, m, u, v, w;
31     cin >> n;
32     for(int i = 1; i < n; i++)
33     {
34         cin >> u >> v >> w;
35         addedge(i << 1, ++u, ++v, w);
36         addedge(i << 1 | 1, v, u, w);
37     }
38     q[++back] = 1, dep[1] = fa[0][1] = 1;
39     while(front != back)
40     {
41         u = q[++front];
42         for(int i = fst[u]; i; i = e[i].nxt)
43             if(e[i].v != fa[0][u])
44             {
45                 q[++back] = e[i].v;
46                 dep[e[i].v] = dep[u] + 1;
47                 fa[0][e[i].v] = u;
48                 dis[e[i].v] = dis[u] + e[i].w;
49             }
50     }
51     for(int i = 1; i <= 16; i++)
52         for(int j = 1; j <= n; j++)
53             fa[i][j] = fa[i - 1][fa[i - 1][j]];
54     cin >> m;
55     while(m--)
56     {
57         cin >> u >> v, u++, v++;
58         cout << dis[u] + dis[v] - 2 * dis[LCA(u, v)] << endl;
59     }
60     return 0;
61 }

View Code

　　Tarjan求LCA, $O(n + m)$（写法较鬼畜）

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 struct edge
 4 {
 5     int v, w, nxt;
 6 }e[100005];
 7 struct query
 8 {
 9     int u, v, nxt;
10 }q[150005];
11 int efst[50005], qfst[75005], fa[50005], lca[75005], dis[50005];
12 bool vis[50005];
13 
14 void addedge(int i, int u, int v, int w)
15 {
16     e[i] = (edge){v, w, efst[u]}, efst[u] = i;
17 }
18 
19 void addquery(int i, int u, int v)
20 {
21     q[i] = (query){u, v, qfst[u]}, qfst[u] = i;
22 }
23 
24 int get_dis(int i)
25 {
26     return dis[q[i << 1].u] + dis[q[i << 1].v] - 2 * dis[lca[i]];
27 }
28 
29 int getfa(int x)
30 {
31     return fa[x] = x == fa[x] ? x : getfa(fa[x]);
32 }
33 
34 void Tarjan(int u)
35 {
36     fa[u] = u, vis[u] = true;
37     for(int i = efst[u]; i; i = e[i].nxt)
38         if(!vis[e[i].v])
39         {
40             dis[e[i].v] = dis[u] + e[i].w;
41             Tarjan(e[i].v);
42             fa[e[i].v] = u;
43         }
44     for(int i = qfst[u]; i; i = q[i].nxt)
45     {
46         int v = q[i].u == u ? q[i].v : q[i].u;
47         if(vis[v]) lca[i >> 1] = getfa(fa[v]);
48     }
49 }
50 
51 int main()
52 {
53     int n, m, u, v, w;
54     cin >> n;
55     for(int i = 1; i < n; i++)
56     {
57         cin >> u >> v >> w;
58         addedge(i << 1, ++u, ++v, w);
59         addedge(i << 1 | 1, v, u, w);
60     }
61     cin >> m;
62     for(int i = 1; i <= m; i++)
63     {
64         cin >> u >> v;
65         addquery(i << 1, ++u, ++v);
66         addquery(i << 1 | 1, v, u);
67     }
68     Tarjan(1);
69     for(int i = 1; i <= m; i++)
70         cout << get_dis(i) << endl;
71     return 0;
72 }

View Code

　　树链剖分求LCA, $O(mlogn)$，我习惯把树剖维护的7个信息写到结构体里。

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 struct edge
 4 {
 5     int v, w, nxt;
 6 }e[100005];
 7 struct point
 8 {
 9     int fa, siz, son, dep, dis, dfn, top;
10 }p[50005];
11 int ptot, fst[50005];
12 
13 void addedge(int i, int u, int v, int w)
14 {
15     e[i] = (edge){v, w, fst[u]}, fst[u] = i;
16 }
17 
18 void DFS1(int u)
19 {
20     p[u].siz = 1;
21     for(int i = fst[u]; i; i = e[i].nxt)
22         if(e[i].v != p[u].fa)
23         {
24             p[e[i].v].fa = u;
25             p[e[i].v].dep = p[u].dep + 1;
26             p[e[i].v].dis = p[u].dis + e[i].w;
27             DFS1(e[i].v);
28             p[u].siz += p[e[i].v].siz;
29             if(p[e[i].v].siz > p[p[u].son].siz)
30                 p[u].son = e[i].v;
31         }
32 }
33 
34 void DFS2(int u, int top)
35 {
36     p[u].dfn = ++ptot, p[u].top = top;
37     if(p[u].son) DFS2(p[u].son, top);
38     for(int i = fst[u]; i; i = e[i].nxt)
39         if(e[i].v != p[u].fa && e[i].v != p[u].son)
40             DFS2(e[i].v, e[i].v);
41 }
42 
43 int LCA(int u, int v)
44 {
45     while(p[u].top != p[v].top)
46     {
47         if(p[p[u].top].dep > p[p[v].top].dep) swap(u, v);
48         v = p[p[v].top].fa;
49     }
50     if(p[u].dep > p[v].dep) swap(u, v);
51     return u;
52 }
53 
54 
55 int main()
56 {
57     int n, m, u, v, w;
58     cin >> n;
59     for(int i = 1; i < n; i++)
60     {
61         cin >> u >> v >> w;
62         addedge(i << 1, ++u, ++v, w);
63         addedge(i << 1 | 1, v, u, w);
64     }
65     p[1].dep = 1, DFS1(1), DFS2(1, 1);
66     cin >> m;
67     while(m--)
68     {
69         cin >> u >> v, u++, v++;
70         cout << p[u].dis + p[v].dis - 2 * p[LCA(u, v)].dis << endl;
71     }
72     return 0;
73 }

View Code

　　LCT, $O(mlog^{2}n)$

  1 #include <bits/stdc++.h>
  2 using namespace std;
  3 struct LCT
  4 {
  5     int fa, c[2], rev, key, sum;
  6     int& operator [] (int i)
  7     {
  8         return c[i];
  9     }
 10 }a[100005];
 11 int sta[100005], top;
 12 
 13 void push_up(int k)
 14 {
 15     a[k].sum = a[a[k][0]].sum + a[a[k][1]].sum + a[k].key;
 16 }
 17 
 18 void push_down(int k)
 19 {
 20     if(a[k].rev)
 21     {
 22         a[a[k][0]].rev ^= 1, a[a[k][1]].rev ^= 1;
 23         swap(a[k][0], a[k][1]), a[k].rev = 0;
 24     }
 25 }
 26 
 27 bool isroot(int x)
 28 {
 29     return a[a[x].fa][0] != x && a[a[x].fa][1] != x;
 30 }
 31 
 32 void rotate(int x)
 33 {
 34     int y = a[x].fa, z = a[y].fa;
 35     int dy = a[y][1] == x, dz = a[z][1] == y;
 36     if(!isroot(y)) a[z][dz] = x;
 37     a[y][dy] = a[x][dy ^ 1], a[a[x][dy ^ 1]].fa = y;
 38     a[x][dy ^ 1] = y, a[y].fa = x, a[x].fa = z;
 39     push_up(y);
 40 }
 41 
 42 void splay(int x)
 43 {
 44     sta[top = 1] = x;
 45     for(int i = x; !isroot(i); i = a[i].fa)
 46         sta[++top] = a[i].fa;
 47     while(top)
 48         push_down(sta[top--]);
 49     while(!isroot(x))
 50     {
 51         int y = a[x].fa, z = a[y].fa;
 52         if(!isroot(y))
 53             if(a[y][1] == x ^ a[z][1] == y) rotate(x);
 54             else rotate(y);
 55         rotate(x);
 56     }
 57     push_up(x);
 58 }
 59 
 60 void access(int x)
 61 {
 62     for(int i = 0; x; x = a[x].fa)
 63         splay(x), a[x][1] = i, i = x;
 64 }
 65 
 66 void make_root(int x)
 67 {
 68     access(x), splay(x), a[x].rev ^= 1;
 69 }
 70 
 71 void link(int x, int y)
 72 {
 73     make_root(x), a[x].fa = y;
 74 }
 75 
 76 void cut(int x, int y)
 77 {
 78     make_root(x), access(y), splay(y), a[y][0] = a[x].fa = 0;
 79 }
 80 
 81 int find_root(int x)
 82 {
 83     access(x), splay(x);
 84     while(a[x][0])
 85         x = a[x][0];
 86     return x;
 87 }
 88 
 89 int main()
 90 {
 91     int n, m, u, v, w;
 92     cin >> n;
 93     for(int i = 1; i < n; i++)
 94     {
 95         cin >> u >> v >> w;
 96         a[i + n].sum = a[i + n].key = w;
 97         link(++u, i + n), link(i + n, ++v);
 98     }
 99     cin >> m;
100     while(m--)
101     {
102         cin >> u >> v;
103         make_root(++u), access(++v), splay(v);
104         printf("%d
", a[v].sum);
105     }
106     return 0;
107 }

View Code