C++14(g++5.4) 解法, 执行用时: 179ms, 内存消耗: 27620K, 提交时间: 2019-05-11 20:52:59

#include "bits/stdc++.h"
using namespace std;
const int N = 1e5 + 10;
int n, m;
vector<int> g[N];
int dfn[N], clk, pos[N], sz[N];
void dfs(int u) {
    dfn[++clk] = u, pos[u] = clk, sz[u] = 1;
    for (int i = 0; i < g[u].size(); ++i) {
        int v = g[u][i];
        dfs(v);
        sz[u] += sz[v];
    }
    // printf("sz[%d] = %d\n", u, sz[u]);
}
int fa[N];
int get(int x) { return x == fa[x] ? x : fa[x] = get(fa[x]); }

void modify(int u, int acc) {
    if (fa[u])
        return fa[get(u)] = get(acc), void();
    else
        fa[u] = u, fa[get(u)] = get(acc);

    for (int i = 0; i < g[u].size(); ++i) {
        int v = g[u][i];
        modify(v, acc);
    }
}
int root[N], sum[N * 20], lc[N * 20], rc[N * 20], tot;
void modify(int &last, int now, int l, int r, int pos) {
    lc[now] = lc[last], rc[now] = rc[last], sum[now] = sum[last] + 1;
    if (l == r)
        return;
    int mid = (l + r) >> 1;
    if (pos <= mid)
        modify(lc[last], lc[now] = ++tot, l, mid, pos);
    else
        modify(rc[last], rc[now] = ++tot, mid + 1, r, pos);
}
int query(int L, int R, int l, int r, int k) {
    int mid = (l + r) >> 1, s = sum[lc[R]] - sum[lc[L]];
    if (l == r)
        return l;
    if (s >= k)
        return query(lc[L], lc[R], l, mid, k);
    else
        return query(rc[L], rc[R], mid + 1, r, k - s);
}
int query(int u) {
    if (!fa[u])
        return u;
    int f = get(u);
    // printf("f = %d sz = %d query: [%d, %d]: %d\n", f, sz[f], pos[f], pos[f] + sz[f] - 1, pos[u] - pos[f] +
    // 1);
    return query(root[pos[f] - 1], root[pos[f] + sz[f] - 1], 1, n, pos[u] - pos[f] + 1);
}
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1, k; i <= n; ++i) {
        scanf("%d", &k);
        for (int j = 1, x; j <= k; ++j) {
            scanf("%d", &x);
            g[i].push_back(x);
        }
    }
    dfs(1);
    // for(int i = 1 ; i <= n ; ++ i) cout << dfn[i] << ' '; cout << endl;
    for (int i = 1; i <= n; ++i) {
        // cout << "tot = " << tot << endl;
        modify(root[i - 1], root[i] = ++tot, 1, n, dfn[i]);
    }
    for (int i = 1, op, u; i <= m; ++i) {
        scanf("%d%d", &op, &u);
        if (op == 1) {
            if (!fa[u])
                modify(u, u);
        } else {
            printf("%d\n", query(u));
        }
    }
}

C++(clang++11) 解法, 执行用时: 179ms, 内存消耗: 6212K, 提交时间: 2021-04-03 10:55:24

#include<bits/stdc++.h>

using namespace std;

const int N=1e5+100;

vector<int> g[N]; 
int dfn[N];
int rnk[N];
int siz[N];
int cnt=0;
void dfs(int x){
	siz[x]=1;
	dfn[x]=++cnt;
	rnk[cnt]=x;
	for(int i=0;i<g[x].size();i++){
		int y=g[x][i];
		dfs(y);
		siz[x]+=siz[y];
	}
}

int vis[N];

int main(){
	int n,q;
	cin>>n>>q;
	for(int i=1;i<=n;i++){
		int k;
		cin>>k;
		for(int j=1;j<=k;j++){
			int x;
			cin>>x;
			g[i].push_back(x);
			vis[x]=1;
		}
	}
	int root;
	for(int i=1;i<=n;i++) if(vis[i]==0) root=i;
	dfs(root);
	while(q--){
		int op,x;
		cin>>op>>x;
		if(op==1) {
			sort(rnk+dfn[x],rnk+dfn[x]+siz[x]);
//			for(int i=1;i<=n;i++)
//				cout<<rnk[i]<<" "<<dfn[i]<<endl;
		}
		else printf("%d\n",rnk[dfn[x]]);
	}  
	return 0;
}