题意:
1.给一个点 加一个儿子编号为n+1
2.询问多个点的LCA
解法:
(1)和两个点LCA类似,找到深度最小的,别的节点都向这这个点条,
在每个节点深度都调整完毕时,如果每个节点都相同那么这个点就是lca
(2)否则,倍增同时向上调整那么最后的所有点的父亲就是LCA
#include
using namespace std;
#define MAXN 3000010
int MAXLOG;
const int INF = 1e8;
const int inf = 1e8;
int T,tot = 1;
char opt[100];
int q[MAXN],dep[MAXN],anc[MAXN][MAXLOG];
inline void update(int x)
{tot+=1;dep[tot]=dep[x]+1;anc[tot][0]=x;for(int i=1;i>j)&1){q[i]=anc[q[i]][j];}}}///****************************bool yes=1;for (int i = 1; i <= k; i++) yes &= (q[i] == q[1]);if(yes)return q[1];for(int i=MAXLOG-1;i>=0;--i){bool tem=1;for(int j=1;j<=k;j++) tem&=(anc[q[j]][i]==anc[q[1]][i]);if(tem)continue;for(int j=1;j<=k;j++) q[j]=anc[q[j]][i];}return anc[q[1]][0];
}
int main()
{
//freopen("input2.txt","r", stdin);scanf("%d",&T);while (T--){int x;scanf("%s%d",&opt,&x);if (opt[0] == 'A') update(x);else{for (int i = 1; i <= x; i++) scanf("%d",&q[i]);printf("%d
",query(x));}}return 0;
}










