hihocoder 1723 : 子树统计（线性基）

本文主要是介绍hihocoder 1723 : 子树统计（线性基），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

描述

给定一棵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

题意：给出一棵树，每次询问给你一个节点x，让你求以x为根的子树集合的所有子集异或和有多少种。

思路：这很明显就是一个线性基的题目，dfs求出以每个节点为子树的线性基的大小cnt，然后2的cnt次幂就是答案。线性基可以合并，从叶子节点开始创建线性基，父亲节点的线性基就为各个子节点的线性基的合并再插入自己的权值。

线性基的讲解：点击打开链接

#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define LL long longusing namespace std;struct LineBasis
{LL b[66];LL p[66];int cnt;LineBasis(){memset(b,0,sizeof(b));memset(p,0,sizeof(p));cnt = 0;}void Insert(LL val){for(int i=60;i>=0;i--){if((1LL<<i)&val){if(b[i] == 0){b[i] = val;break;}val ^= b[i];}}if(val > 0)cnt++;}LineBasis Merge(LineBasis n1,LineBasis n2){LineBasis ret = n1;for(int i=0;i<=60;i++)if(n2.b[i])ret.Insert(n2.b[i]);return ret;}
};LineBasis num[100010];vector<int> v[100010];
LL a[100010];void dfs(int x)
{for(int i=0;i<v[x].size();i++){int xx = v[x][i];dfs(xx);num[x] = num[x].Merge(num[x],num[xx]);}num[x].Insert(a[x]);
}
int main(void)
{int n,q,i,j;while(scanf("%d%d",&n,&q)==2){for(i=1;i<=n;i++)v[i].clear();for(i=2;i<=n;i++){int x;scanf("%d",&x);v[x].push_back(i);}for(i=1;i<=n;i++){scanf("%lld",&a[i]);}dfs(1);while(q--){int x;scanf("%d",&x);int cnt = num[x].cnt;LL ans = 1;for(i=1;i<=cnt;i++)ans *= 2;printf("%lld\n",ans);}}return 0;
}

这篇关于hihocoder 1723 : 子树统计（线性基）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！