markdown namespace tar main roo can 现在 oid const
原题:我是传送门
题解:
- #include <cstdio>
- #include <cstring>
- using namespace std;
- const int N=500010;
- struct ques {int next,to,ans;};
- struct edge {int next,to;};
- edge G[N<<1];
- int head_G[N],tot;
- int add_G(int a,int b) {
- G[++tot]=(edge) {head_G[a],b};
- head_G[a]=tot;
- G[++tot]=(edge) {head_G[b],a};
- head_G[b]=tot;
- }
- ques Q[N<<1];
- int head_Q[N],cnt=1;
- void add_Q(int a,int b) {
- Q[++cnt]=(ques) {head_Q[a],b};
- head_Q[a]=cnt;
- Q[++cnt]=(ques) {head_Q[b],a};
- head_Q[b]=cnt;
- }
- int fa[N];
- int find(int x) {
- return x==fa[x]?x:fa[x]=find(fa[x]);
- }
- bool book[N];
- void dfs(int u) {
- book[fa[u]=u]=1;
- for(int i=head_G[u];i;i=G[i].next) {
- if(!book[G[i].to]) dfs(G[i].to),fa[G[i].to]=u;
- }
- for(int i=head_Q[u];i;i=Q[i].next) {
- if(book[Q[i].to]) Q[i].ans=Q[i^1].ans=find(Q[i].to);
- }
- }
- int n,m,root;
- int main() {
- scanf("%d%d%d",&n,&m,&root);
- for(int i=1,a,b;i<n;i++) {
- scanf("%d%d",&a,&b),add_G(a,b);
- }
- for(int i=1,a,b;i<=m;i++) {
- scanf("%d%d",&a,&b),add_Q(a,b);
- }
- dfs(root);
- for(int i=1;i<=m;i++) {
- printf("%d\n",Q[i<<1].ans);
- }
- return 0;
- }
[Tarjan] P3379 最近公共祖先
来源: http://www.bubuko.com/infodetail-2409818.html