学习自 : 大佬博客
题意： 给一棵树，每一个节点上有多个权值，q次询问，求对于某一个节点，从其自身到根节点的路径上第一个含有给定权值的点的编号；
思路：对每一个权值建立一颗线段树，然后用线段树维护区间最大值即可求解.
#include <iostream> using namespace std; const int N = 1e5 + 10, MAXN = 3e7 + 10; struct edge { int to, next; }Edge[N<<1]; int cnt, head[N]; int num[N], top[N], f[N], son[N], dep[N], id[N]; int lc[MAXN], rc[MAXN], R[MAXN], MAX[MAXN]; //用R[]来储存每一个线段树的根节点，通过lc[]与rc[]使线段树互相独立; inline int max(int a,int b){ return a > b ? a : b; } inline void add_edge(int from,int to) { Edge[++cnt].to = to; Edge[cnt].next = head[from]; head[from] = cnt; } inline void dfs1(int v) { num[v] = 1; dep[v] = dep[f[v]] + 1; for(int i = head[v]; i; i = Edge[i].next){ int to = Edge[i].to; f[to] = v; dfs1(to); num[v] += num[to]; if(num[to] > num[son[v]]) son[v] = to; } } inline void dfs2(int v,int tp) { top[v] = tp; id[v] = ++cnt; if(!son[v]) return ; dfs2(son[v], tp); for(int i = head[v]; i; i = Edge[i].next){ int to = Edge[i].to; if(to == son[v]) continue; dfs2(to,to); } } inline void update(int L,int C,int l,int r,int &rt) { if(!rt){ rt = ++cnt; MAX[rt] = C; } MAX[rt] = max(MAX[rt], C); if(l == r) return ; int m = (l+r)>>1; if(L <= m) update(L,C,l,m,lc[rt]); else update(L,C,m+1,r,rc[rt]); } inline int query(int L,int R,int l,int r,int rt) { if(!rt) return 0; if(L <= l && r <= R) return MAX[rt]; int m = (l+r)>>1, ans = 0; if(L <= m) ans = max(ans, query(L,R,l,m,lc[rt])); if(m < R) ans = max(ans, query(L,R,m+1,r,rc[rt])); return ans; } inline int querys(int A,int x) { int ans = 0; while(top[A] != top[1]){ ans = max(ans, query(id[top[A]],id[A],1,1e6,R[x])); A = f[top[A]]; } return max(ans, query(id[1],id[A],1,1e6,R[x])); } int main() { ios::sync_with_stdio(false); cin.tie(0), cout.tie(0); int n, m, q, A, B; cin>>n; for(int i = 2; i <= n; ++i){ cin>>A; add_edge(A,i); } cnt = 0; dfs1(1); dfs2(1,1); cnt = 0; for(int i = 1; i <= n; ++i){ cin>>m; for(int j = 0; j < m; ++j){ cin>>A; update(id[i],i,1,1e6,R[A]); }//因为题目保证了(1 <= pi <= i - 1) 因此此处可直接用类的编号来更新，否则需要用类新的编号来更新; } cin>>q; for(int i = 0; i < q; ++i){ cin>>A>>B; int ans = querys(A,B); if(ans == 0) cout<<-1<<'\n'; else cout<<ans<<'\n'; } return 0; }呜呜呜，从知道这篇博客到会写这份代码过了一个多月的时间（爽）
