题干：

时间限制:10000ms

单点时限:1000ms

内存限制:256MB

描述

给定一棵N个节点的有根树，树上每个节点有一个非负整数权重Wi。定义节点集合S={i1, i2, ……, ir}的总权重为：(⊕是异或运算)

每次询问一棵子树内所有可能出现的总权重数量，即令E为所询问的子树内节点的集合，

|T|即为可能出现的总权重数量。

输入

第一行包含两个整数N，Q，表示树的节点数目和询问数目，节点1总是这棵树的根部。

第二行包含N-1个整数，第i个整数P_i表示i+1号节点的父亲节点。数据保证Pi≤i。

第三行包含N个整数，表示每个节点的权重Wi。

第四行包含Q个整数，每个整数Qi表示询问子树Qi内的可能出现的总权重数量

N≤100000，Q≤100000，Wi≤260

输出

输出共Q行，每行包含一个整数T表示子树Qi内可能出现的总权重数量

样例输入

7 3
1 2 2 1 5 5
8 4 3 1 2 4 6
2 5 1

样例输出

8
4
16

 

解题报告：

    dfs一遍求出以每个节点为根节点的线性基大小，设为sz，那么2^sz就是当前查询的答案。因为查询次数不多，里面可以带个log，所以不需要提前预处理出来。每次直接计算sz的大小就行了。往前回溯的时候顺便给合并这两个线性基。

AC代码：（451ms）

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<map>
#include<vector>
#include<set>
#include<string>
#include<cmath>
#include<cstring>
#define ll long long
#define pb push_back
#define pm make_pair
using namespace std;
const int MAX = 2e5 + 5;
int n,q,fa[MAX];
vector<int> vv[MAX];
const int Bit = 64;
ll Base[MAX][66];
ll w[MAX],db[123];
void insert(int cur,ll x) {
	for(int j = Bit-1; j>=0; j--) {
		if(x>>j & 1) {
			if(Base[cur][j] == 0) {
				Base[cur][j] = x;break;
			}
			else x ^= Base[cur][j];
		}
	}
}
void merge(int cur,int rt) {
	for(int j = Bit-1; j>=0; j--) {
		if(Base[cur][j]) {
			insert(rt,Base[cur][j]);
		}
	}
} 
void dfs(int cur,int rt) {
	int up = vv[cur].size();
	for(int i = 0; i<up; i++) {
		int v = vv[cur][i];
		if(v == rt) continue;
		dfs(v,cur);
		merge(v,cur);
	}
	insert(cur,w[cur]);
}
int main()
{
	db[0] = 1;
	for(int i = 1; i<=66; i++) db[i] = db[i-1]*2;
	cin>>n>>q;
	for(int i = 2; i<=n; i++) {
		scanf("%d",&fa[i]);
		vv[fa[i]].pb(i);
	}
	for(int i = 1; i<=n; i++) scanf("%lld",w+i);
	dfs(1,0);
	while(q--) {
		int x;
		scanf("%d",&x);
		int sz = 0;
		for(int j = 0; j<=Bit-1; j++) {
			if(Base[x][j]) sz++;
		}
		printf("%lld\n",db[sz]);
	}
	return 0 ;
 }