怎么把在微企点做响应式网站,做网站赚钱什么类型,电影频道做的网站广告,js网站模板怎么用题干#xff1a;
时间限制:10000ms
单点时限:1000ms
内存限制:256MB
描述
给定一棵N个节点的有根树#xff0c;树上每个节点有一个非负整数权重Wi。定义节点集合S{i1, i2, ……, ir}的总权重为#xff1a;(⊕是异或运算) 每次询问一棵子树内所有可能出现的总权重数量
时间限制:10000ms
单点时限:1000ms
内存限制:256MB
描述
给定一棵N个节点的有根树树上每个节点有一个非负整数权重Wi。定义节点集合S{i1, i2, ……, ir}的总权重为(⊕是异或运算) 每次询问一棵子树内所有可能出现的总权重数量即令E为所询问的子树内节点的集合 |T|即为可能出现的总权重数量。
输入
第一行包含两个整数NQ表示树的节点数目和询问数目节点1总是这棵树的根部。
第二行包含N-1个整数第i个整数P_i表示i1号节点的父亲节点。数据保证Pi≤i。
第三行包含N个整数表示每个节点的权重Wi。
第四行包含Q个整数每个整数Qi表示询问子树Qi内的可能出现的总权重数量
N≤100000Q≤100000Wi≤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
#includecstdio
#includeiostream
#includealgorithm
#includequeue
#includemap
#includevector
#includeset
#includestring
#includecmath
#includecstring
#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];
vectorint 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; j0; j--) {if(xj 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; j0; 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; iup; 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; i66; i) db[i] db[i-1]*2;cinnq;for(int i 2; in; i) {scanf(%d,fa[i]);vv[fa[i]].pb(i);}for(int i 1; in; i) scanf(%lld,wi);dfs(1,0);while(q--) {int x;scanf(%d,x);int sz 0;for(int j 0; jBit-1; j) {if(Base[x][j]) sz;}printf(%lld\n,db[sz]);}return 0 ;}