-
个人简介
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; struct zzz { int t, nex; }e[500010 << 1]; int head[500010], tot; void add(int x, int y) { e[++tot].t = y; e[tot].nex = head[x]; head[x] = tot; } int depth[500001], fa[500001][22], lg[500001]; void dfs(int now, int fath) { fa[now][0] = fath; depth[now] = depth[fath] + 1; for(int i = 1; i <= lg[depth[now]]; ++i) fa[now][i] = fa[fa[now][i-1]][i-1]; for(int i = head[now]; i; i = e[i].nex) if(e[i].t != fath) dfs(e[i].t, now); } int LCA(int x, int y) { if(depth[x] < depth[y]) swap(x, y); while(depth[x] > depth[y]) x = fa[x][lg[depth[x]-depth[y]] - 1]; if(x == y) return x; for(int k = lg[depth[x]] - 1; k >= 0; --k) if(fa[x][k] != fa[y][k]) x = fa[x][k], y = fa[y][k]; return fa[x][0]; } int main() { int n, m, s; scanf("%d%d%d", &n, &m, &s); for(int i = 1; i <= n-1; ++i) { int x, y; scanf("%d%d", &x, &y); add(x, y); add(y, x); } for(int i = 1; i <= n; ++i) lg[i] = lg[i-1] + (1 << lg[i-1] == i); dfs(s, 0); for(int i = 1; i <= m; ++i) { int x, y; scanf("%d%d",&x, &y); printf("%d\n", LCA(x, y)); } return 0; }
-
通过的题目
- P82
- P88
- P90
- P99
- P101
- P105
- P106
- P108
- P109
- P114
- P119
- P123
- P127
- P137
- P142
- P143
- P144
- P146
- P149
- P152
- P154
- P155
- P156
- P157
- P161
- P182
- P183
- P184
- P208
- P212
- P214
- P220
- P238
- P241
- P243
- P246
- P248
- P260
- P267
- P268
- P273
- P276
- P283
- P284
- P285
- P297
- P298
- P304
- P306
- P308
- P309
- P310
- P311
- P314
- P317
- P319
- P320
- P326
- P328
- P329
- P334
- P335
- P337
- P340
- P355
- P385
- P387
- P391
- P431
- P432
- P433
- P436
- P442
- P456
- P459
- P464
- P465
- P466
- P467
- P477
- P514
- P517
- P533
- P561
- P562
- P606
- P613
- P614
- P615
- P616
- P617
- P625
- P626
- P642
- P643
- P653
- P657
- P658
- P659
- P663
- P666
- P667
- P668
- P682
- P683
- P684
- P700
- P701
- P702
- P703
- P707
- P713
- P714
- P716
- P717
- P723
- P733
- P743
- P748
- P761
- P768
- P769
- P773
- P774
- P786
- P787
- P821
- P828
- P829
- P837
- P862
- P877
- P938
- P955
- P958
- P966
- P968
- P970
- P975
- P1009
- P1036
- P1037
- P1064
- P1077
- P1092
- P1110
- P1127
- P1138
- P1157
- P1158
- P1193
- P1198
- P1208
- P1381
- P1382
- P1599
- P1811
- P1852
- P1863
- P1868
- P1869
- P1888
- P1898
- P1899
- P1900
- P1901
- P1902
- P1904
- P1910
- P1911
- P1926
- P1934
- P1938
- P1939
- P1940
- P1941
- P1968
- P1970
- P1971
- P1972
- P1974
- P1977
- P1978
- P1979
- P1983
- P1997
- P2004
- P2009
- P2011
- P2012
- P2013
- P2019
- P2020
- P2023
- P2032
- P2033
- P2039
- P2043
- P2045
- P2059
- P2078
- P2113
- P2161
- P2204
- P2209
- P2214
- P2238
- P2261
- P2276
- P2281
- P2351
- P2644
- P2651
- P2652
- P2680
- P2708
- P2852
- P2859
- P2860
- P2873
- P2892
-
最近活动
- C2025届2024年1月27日-寒假集训 作业
- C2025届2023年10月20日练习_STL 作业
- C2025届2023年暑期练习 作业
- C2025届普及组一阶总复习(20230715) 作业
- C2025届普及组一阶测试(20230715) OI
- C2025届普及组一阶基础知识测试(20230610) OI
- C2025届普及组一阶中期测试(20230605) OI
- C2025届循环结构练习3周日班(20230521) 作业
- C2025届循环结构练习3周六班(20230521) 作业
- C2025届循环结构练习2周六班(20230516) 作业
- C2025届循环结构练习2周日班(20230516) 作业
- C2025届选择结构练习周六班(20230413) 作业
题目标签
- 基础语法
- 66
- 分支问题
- 51
- 基础问题
- 41
- 顺序结构
- 33
- 简单循环
- 33
- 字符串
- 23
- 数组问题
- 20
- 入门
- 17
- 递归
- 17
- 普及组
- 17
- 嵌套循环
- 15
- 需要找规律的循环
- 14
- dfs
- 14
- 文件重定向
- 12
- 数论
- 12
- 素数判定
- 12
- 搜索
- 12
- noip
- 11
- 循环
- 10
- 二维数组
- 9