LCA 資料: http://www.cnblogs.com/zgmf_x20a/archive/2008/10/15/1311313.html

雖然網上這方面資料很多了， 不過自己練習后還是寫下。。。

POJ?1330?Nearest?Common?Ancestors

輸入N-1條邊，建一個樹，然后是一個LCA查詢，只有一次，樸素做比較快。

樹是唯一的。

POJ?1470?Closest?Common?Ancestors

和上一題非常類似，不過點變少了，查詢次數變多了，因為n<=900樸素就可以了。

POJ?1986?Distance?Queries

查詢從u-v的距離。

根據輸入建一個樹，以任意點位根都可以，距離是不變的。

然后每個節點保存到根的距離dis[]，這樣結果可以就是

dis[u]?+?dis[v]?-?2?*?dis[lca(u,?v)];?去掉重復的與無用的。。

POJ?3728?The?merchant

給出n個點買入與賣出商品的價格，然后給出n-1條邊。?問：?

從u-v上進行一次交易，可以選一個在u-v之間的點買入，然后再這個點之后的點賣出，的最大獲益，既買入價格-賣出價格。

可以考慮這么做：

求出lca(u,?v)，?這樣問題可以分解為u?-?lca(u,?v)的最大獲益,?lca(u,?v)的最大獲益，以及u?-?lca(u,?v)的最大值?-?lca(u,?v)?-?v的最小值，?中的最大值。

可以用類似求lca的DP求出最大值、最小值，最大獲益，最小獲益(考慮方向)。

POJ?3237?Tree

題意：

CHANGE?i?v?Change?the?weight?of?the?ith?edge?to?v

NEGATE?a?b?Negate?the?weight?of?every?edge?on?the?path?from?a?to?b

QUERY?a?b?Find?the?maximum?weight?of?edges?on?the?path?from?a?to?b

很清楚了。。

沒有什么特別的想法，但數據比較水，直接log(n)求lca(u,v)然后修改所有

u?-?lca(u,v),?v?-?lca(u,?v)就可以水過去...

POJ?2763?Housewife?Wind

在搜索的時候記錄點第一次出現位置LT[]，與結束位置RT[],這樣對u?-?v邊得修改，?影響的值是LT[u]?-?RT[u],?區間問題，?可以用樹狀數組解決。

因為dis[u]?+?dis[v]?-?2?*?dis[lca(u,?v)]所以這里只有修改V[LT[u]]?+?change，

和?V[RT[u]?+?1]?-?change，就可以了。?最后查詢是的結果是sum(LT[u])?+?sum(LT[v])?-?2?*?sum(LT[lca(u,?v)]);?注意這里修改的是change，?與輸出的v有區別的。?初始化可以當做是從0-v的change，?同樣處理就可以了。?不過開10W一直RE，?改20W就AC了。。。。

POJ?3368?Frequent?values

用RMQ做的，沒線段樹有效率。因為輸入有序的，可以考慮把點合并成個數與值,

然后查詢就變成查cnt最大的的RMQ問題了，?注意出發點，與結束點的區間分解。

ZOJ?3195?Design?the?city

和POJ?1986?Distance?Queries類似，?變成三個點的距離了。

結果是?(dis[a]?-?dis[ab]?+?dis[a]?-?dis[ac]?+

????????dis[b]?-?dis[ab]?+?dis[b]?-?dis[bc]?+

????????dis[c]?-?dis[ac]?+?dis[c]?-?dis[bc])?/?2;

HDU?2586?How?far?away

和POJ?1986?Distance?Queries一樣。。。

View Code 1 //vector 會超時
2 const int MAXN = 200200;
3 const int MAXNLOG = 20;
4 struct Node {
5 int first;
6 int second;
7 }g[MAXN<<1];
8 int nxt[MAXN], head[MAXN], ne;
9 int dep[MAXN];
10 int pa[MAXN][MAXNLOG], dis[MAXN];
11 int LT[MAXN], RT[MAXN], id;
12
13 inline void addedge(int u, int v, int w) {
14 g[ne].first = v, g[ne].second = w;
15 nxt[ne] = head[u]; head[u] = ne++;
16 g[ne].first = u, g[ne].second = w;
17 nxt[ne] = head[v]; head[v] = ne++;
18 }
19
20 void dfs(int u, int fa, int d, int v) {
21 dis[u] = v, dep[u] = d, pa[u][0] = fa;
22 LT[u] = id++;
23 for (int i = head[u]; i != -1; i = nxt[i]) {
24 if (g[i].first != fa) {
25 dfs(g[i].first, u, d + 1, v + g[i].second);
26 }
27 }
28 RT[u] = id;
29 }
30
31 void process(int n) {
32 for (int i = 0; i < n; ++i) {
33 for (int j = 0; (1 << j) < n; ++j) {
34 pa[i][j] = -1;
35 }
36 }
37 id = 1;
38 dfs(0, 0, 0, 0);
39 for (int j = 1; (1 << j) < n; ++j) {
40 for (int i = 0; i < n; ++i) {
41 if (pa[i][j-1] != -1) {
42 pa[i][j] = pa[pa[i][j-1]][j-1];
43 }
44 }
45 }
46 }
47
48 int lca(int a, int b) {
49 if (dep[a] < dep[b]) {
50 swap(a, b);
51 }
52 int tmp = 1;
53 for (; (1 << tmp) <= dep[a]; ++tmp);
54 --tmp;
55 for (int i = tmp; i >= 0; --i) {
56 if (dep[a] - (1 << i) >= dep[b]) {
57 a = pa[a][i];
58 }
59 }
60 if (a == b) {
61 return a;
62 }
63 for (int i = tmp; i >= 0; --i) {
64 if (pa[a][i] != -1 && pa[a][i] != pa[b][i]) {
65 a = pa[a][i], b = pa[b][i];
66 }
67 }
68 return pa[a][0];
69 }
70
71 int n, dfn[MAXN];
72 int road[MAXN][3];
73 inline void add(int x, int v) {
74 while (x <= n) {
75 dfn[x] += v;
76 x += x & -x;
77 }
78 }
79
80 inline int sum(int x) {
81 int ret = 0;
82 while (x > 0) {
83 ret += dfn[x];
84 x -= x & -x;
85 }
86 return ret;
87 }
88
89 int main () {
90 while (true) {
91 n = nextInt();
92 int q = nextInt();
93 int s = nextInt() - 1;
94 ne = 0, memset(head, -1, sizeof(head));
95 //g.clear(); g.resize(n);
96 for (int i = 0; i < n - 1; ++i) {
97 int a = nextInt() - 1;
98 int b = nextInt() - 1;
99 int w = nextInt();
100 addedge(a, b, w);
101 //g[a].push_back(MP(b, w));
102 //g[b].push_back(MP(a, w));
103 road[i][0] = a, road[i][1] = b, road[i][2] = w;
104 }
105 process(n);
106 while (q--) {
107 int ope = nextInt();
108 if (ope == 0) {
109 int v = nextInt() - 1;
110 int l = lca(s, v);
111 int d = dis[s] + dis[v] - 2 * dis[l];
112 d += sum(LT[s]) + sum(LT[v]) - 2 * sum(LT[l]);
113 printf("%d\n", d);
114 s = v;
115 }
116 else {
117 int x = nextInt() - 1;
118 int v = nextInt();
119 int index = road[x][0];
120 if (dep[index] < dep[road[x][1]]) {
121 index = road[x][1];
122 }
123 int c = v - road[x][2];
124 road[x][2] = v;
125 add(LT[index], c);
126 add(RT[index], -c);
127 }
128 }
129 }
130 return 0;
131 }

轉載于:https://www.cnblogs.com/carber/archive/2011/06/13/2079869.html

總結

以上是生活随笔為你收集整理的LCA 练习总结的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。