题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=5165
题意:见原题面。
树上多点 lca 为其中 dfn 最大/最小值的 lca。
丧心病狂卡 log.... 好像还是我第一次写 tarjan...
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 |
#include <cmath> #include <queue> #include <cstdio> #include <iomanip> #include <cstdlib> #include <cstring> #include <iostream> #include <algorithm> #define N 3000010 #define Q 1010 #define ll long long #define inf 1000000010 using namespace std; #define fstc __attribute__((optimize("-O3"))) #define IL __inline__ __attribute__((always_inline)) char xB[1<<15],*xS=xB,*xT=xB; #define getchar() (xS==xT&&(xT=(xS=xB)+fread(xB,1,1<<15,stdin),xS==xT)?0:*xS++) #define OUT 10000000 char Out[OUT],*ou=Out; int Outn[30],Outcnt; fstc IL void write(int x) { if(!x)*ou++=48; else { for(Outcnt=0;x;x/=10)Outn[++Outcnt]=x%10+48; while(Outcnt)*ou++=Outn[Outcnt--]; } } fstc IL int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n=1,m; int dfn[N]; struct zgz { int next,to; }edge[N]; int head[N],cnt=1; vector<pair<int,int> > p[N]; fstc void add(int from,int to) { edge[cnt].to=to; edge[cnt].next=head[from]; head[from]=cnt++; } int q[Q][Q],len[Q],top; int ans[N],tim; fstc void dfs_n(int x) { dfn[x]=++tim; for(int i=head[x];i;i=edge[i].next) { int to=edge[i].to; dfs_n(to); } } int fa[N],vis[N]; fstc int find(int x) {return fa[x]==x?x:fa[x]=find(fa[x]);} fstc void dfs(int x) { fa[x]=x; for(int i=head[x];i;i=edge[i].next) { int to=edge[i].to; dfs(to),fa[to]=x; } vis[x]=1; for(int i=0;i<p[x].size();i++) if(vis[p[x][i].first])ans[p[x][i].second]=find(p[x][i].first); } fstc int main() { m=read(); while(m--) { char opt=getchar(); while(opt!='A'&&opt!='Q')opt=getchar(); if(opt=='A') { int x=read(); add(x,++n); } else { int k=read(); len[++top]=k; for(int i=1;i<=k;i++)q[top][i]=read(); } } dfs_n(1); for(int i=1;i<=top;i++) { int mn=q[i][1],mx=q[i][1]; if(len[i]==1) { ans[i]=q[i][1]; continue ; } for(int j=1;j<=len[i];j++) { if(dfn[q[i][j]]>dfn[mx])mx=q[i][j]; if(dfn[q[i][j]]<dfn[mn])mn=q[i][j]; } p[mn].push_back(make_pair(mx,i)); p[mx].push_back(make_pair(mn,i)); } dfs(1); for(int i=1;i<=top;i++)write(ans[i]),*ou++='\n'; fwrite(Out,1,ou-Out,stdout); } |
Comments | 2 条评论
其实只有 1000 个询问的话 把 DFS 序最左边的和最右边的拿出来求一下就行了
@Edw
啥意思?