P3379 \u3010\u6a21\u677f\u3011\u6700\u8fd1\u516c\u5171\u7956\u5148\uff08LCA\uff09<\/a><\/p>\n\u500d\u589e\u601d\u60f3\u3002dp[i][j]\u8868\u793a\u7ed3\u70b9i\u7684\u8ddd\u81ea\u5df1\u957f\u5ea6\u4e3a2^j<\/code>\u7684\u7956\u5148
\ndp[i][j] = dp[dp[i][j-1]][j-1]<\/p>\n#include <cstdio>\n#include <algorithm>\n#include <cstring>\n#include <vector>\nusing namespace std;\nconst int maxn = 5e5+5;\nint n, m, s;\nvector<int> G[maxn];\nint dp[maxn][27];\nint fa[maxn], high[maxn];\nint lg[maxn];\ninline int LCA(int u, int v){\n if (high[u] < high[v]) swap(u, v);\n while (high[u] > high[v]) u = dp[u][lg[high[u]-high[v]]-1];\n if (u==v) return u;\n for (int k=lg[high[u]]-1; k>=0; k--) if (dp[u][k] != dp[v][k])\n u = dp[u][k], v = dp[v][k];\n return dp[u][0];\n}\nvoid dfs(int x, int y){ \/\/ x\u7684\u7236\u4eb2\u7ed3\u70b9\u662fy\n fa[x] = y;\n high[x] = high[y] + 1;\n for (int i=0; i<G[x].size(); i++) if (!high[G[x][i]])\n dfs(G[x][i], x);\n return;\n}\ninline int read(){\n int x=0; char ch = getchar();\n while (ch<'0' || ch>'9') ch = getchar();\n while (ch>='0'&& ch<='9'){\n x = x*10 + ch-'0';\n ch = getchar();\n }\n return x;\n}\nint main(){\n int x, y, u, v;\n n = read(), m = read(), s = read();\n for (int i=1; i<n; i++){\n x = read(), y = read();\n G[x].push_back(y);\n G[y].push_back(x);\n }\n dfs(s, 0);\n for (int i=1; i<=n; i++)\n lg[i] = lg[i-1] + (1<<lg[i-1] == i);\n for (int j=1; j<=n; j++) dp[j][0] = fa[j];\n for (int k=1; k<lg[n]; k++){\n for (int j=1; j<=n; j++){\n dp[j][k] = dp[dp[j][k-1]][k-1];\n }\n }\n for (int i=1; i<=m; i++){\n u = read(), v = read();\n printf ("%d\\n", LCA(u, v));\n }\n return 0;\n}<\/code><\/pre>\n\u4e00\u4e2a\u6c42log2(i)+1\u7684\u5feb\u901f\u65b9\u6cd5\u3002<\/p>\n
for (int i=1; i<=n; i++)\n lg[i] = lg[i-1] + (1<<lg[i-1] == i);<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"\u6700\u8fd1\u516c\u5171\u7956\u5148 P3379 \u3010\u6a21\u677f\u3011\u6700\u8fd1\u516c\u5171\u7956\u5148\uff08LCA\uff09 \u500d\u589e\u601d\u60f3\u3002dp[i][j]\u8868\u793a\u7ed3\u70b9i\u7684\u8ddd\u81ea […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[56],"tags":[],"_links":{"self":[{"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/posts\/733"}],"collection":[{"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/comments?post=733"}],"version-history":[{"count":5,"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/posts\/733\/revisions"}],"predecessor-version":[{"id":738,"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/posts\/733\/revisions\/738"}],"wp:attachment":[{"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/media?parent=733"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/categories?post=733"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/tags?post=733"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}