SXCPC2018 nucoj2004 国王的怪癖

可持久化trie。考场上我脑补了一个trie树合并也A了
#include <iostream>

#include <cstring>

#include <cstdio>

using namespace std;

int n, k, m, dfnl[100005], dfnr[100005], idx, rot[100005], v[100005], uu, vv, cnt;

int hea[100005], fan[100005], tot;

struct Edge{

	int too, nxt, val;

}edge[200005];

struct Node{

	int l, r, sum;

}nd[3333333];

void add_edge(int fro, int too){

	edge[++cnt].nxt = hea[fro];

	edge[cnt].too = too;

	hea[fro] = cnt;

}

void dfs(int x, int f){

	dfnl[x] = ++idx;

	fan[idx] = x;

	for(int i=hea[x]; i; i=edge[i].nxt){

		int t=edge[i].too;

		if(t!=f)	dfs(t, x);

	}

	dfnr[x] = idx;

}

int update(int pre, int x, int p){

	int re=++tot;

	nd[re] = nd[pre];

	nd[re].sum++;

	if(p<0)

		return re;

	int tmp=(x>>p)&1;

	if(tmp)	nd[re].r = update(nd[pre].r, x, p-1);

	else	nd[re].l = update(nd[pre].l, x, p-1);

	return re;

}

int query(int pre, int now, int x, int p){

	if(p<0)	return 0;

	int tmp=(x>>p)&1;

	if(tmp){

		int sum=nd[nd[now].l].sum-nd[nd[pre].l].sum;

		if(sum)

			return query(nd[pre].l, nd[now].l, x, p-1)+(1<<p);

		else

			return query(nd[pre].r, nd[now].r, x, p-1);

	}

	else{

		int sum=nd[nd[now].r].sum-nd[nd[pre].r].sum;

		if(sum)

			return query(nd[pre].r, nd[now].r, x, p-1)+(1<<p);

		else

			return query(nd[pre].l, nd[now].l, x, p-1);

	}

}

int main(){

	while(scanf("%d %d %d", &n, &k, &m)!=EOF){

		memset(hea, 0, sizeof(hea));

		idx = tot = cnt = 0;

		for(int i=1; i<=n; i++)

			scanf("%d", &v[i]);

		for(int i=1; i<n; i++){

			scanf("%d %d", &uu, &vv);

			add_edge(uu, vv);

			add_edge(vv, uu);

		}

		dfs(k, 0);

		for(int i=1; i<=n; i++)

			rot[i] = update(rot[i-1], v[fan[i]], 30);

		while(m--){

			scanf("%d %d", &uu, &vv);

			printf("%d\n", query(rot[dfnl[uu]-1], rot[dfnr[uu]], vv, 30));

		}

	}

	return 0;

}
巴特西

SXCPC2018 nucoj2004 国王的怪癖

最新文章

热门文章
