Tree Cutting
题目连接:
http://acm.hdu.edu.cn/showproblem.php?pid=5909
Description
Byteasar has a tree T with n vertices conveniently labeled with 1,2,...,n. Each vertex of the tree has an integer value vi.
The value of a non-empty tree T is equal to v1⊕v2⊕...⊕vn, where ⊕ denotes bitwise-xor.
Now for every integer k from [0,m), please calculate the number of non-empty subtree of T which value are equal to k.
A subtree of T is a subgraph of T that is also a tree.
Input
The first line of the input contains an integer T(1≤T≤10), denoting the number of test cases.
In each test case, the first line of the input contains two integers n(n≤1000) and m(1≤m≤210), denoting the size of the tree T and the upper-bound of v.
The second line of the input contains n integers v1,v2,v3,...,vn(0≤vi<m), denoting the value of each node.
Each of the following n−1 lines contains two integers ai,bi, denoting an edge between vertices ai and bi(1≤ai,bi≤n).
It is guaranteed that m can be represent as 2k, where k is a non-negative integer.
Output
For each test case, print a line with m integers, the i-th number denotes the number of non-empty subtree of T which value are equal to i.
The answer is huge, so please module 109+7.
Sample Input
2
4 4
2 0 1 3
1 2
1 3
1 4
4 4
0 1 3 1
1 2
1 3
1 4
Sample Output
3 3 2 3
2 4 2 3
Hint
题意
给你一棵树,然后问你,里面有多少个连通块的异或和为j
题解:
树形DP去做,然后我们考虑转移,用fwt去进行优化就好了
至于为什么这么变换的。。。。
俺也不是很清楚:http://picks.logdown.com/posts/179290-fast-walsh-hadamard-transform
代码
#include<bits/stdc++.h>
using namespace std;
const int mod = 1e9+7;
const int inv = (mod+1)/2;
const int maxn = 3005;
int n,m,ans[maxn],val[maxn];
vector<int> E[maxn];
long long dp[maxn][maxn],tmp[maxn],a[maxn],b[maxn];
void fwt(long long *aa,int l,int r)
{
if(r-l==1)return;
int mid=(l+r)/2;
fwt(aa,l,mid);
fwt(aa,mid,r);
int len=mid-l;
for(int i=l;i<mid;i++)
{
long long x1=aa[i];
long long x2=aa[i+len];
aa[i]=(x1+x2)%mod;
aa[i+len]=(x1-x2+mod)%mod;
}
}
void ifwt(long long *aa,int l,int r)
{
if(r-l==1)return;
int mid=(l+r)/2;
int len=mid-l;
for(int i=l;i<mid;i++)
{
long long y1=aa[i];
long long y2=aa[i+len];
aa[i]=(y1+y2)*inv%mod;
aa[i+len]=((y1-y2+mod)%mod*inv)%mod;
}
ifwt(aa,l,mid);
ifwt(aa,mid,r);
}
void solve(long long *aa,long long *bb)
{
memcpy(a,aa,sizeof(long long)*m);
memcpy(b,bb,sizeof(long long)*m);
fwt(a,0,m);
fwt(b,0,m);
memset(tmp,0,sizeof(tmp));
for(int i=0;i<m;i++)
tmp[i]=a[i]*b[i]%mod;
ifwt(tmp,0,m);
}
void dfs(int x,int f)
{
memset(dp[x],0,sizeof(dp[x]));
dp[x][val[x]]=1;
for(int i=0;i<E[x].size();i++){
int v=E[x][i];
if(v==f)continue;
dfs(v,x);
solve(dp[x],dp[v]);
for(int j=0;j<m;j++)(dp[x][j]+=tmp[j])%=mod;
}
for(int i=0;i<m;i++)(ans[i]+=dp[x][i])%=mod;
}
void solve()
{
scanf("%d%d",&n,&m);
for(int i=0;i<m;i++)ans[i]=0;
for(int i=1;i<=n;i++)scanf("%d",&val[i]),E[i].clear();
for(int i=1;i<n;i++)
{
int x,y;
scanf("%d%d",&x,&y);
E[x].push_back(y);
E[y].push_back(x);
}
dfs(1,0);
for(int i=0;i<m;i++)
{
if(i==0)printf("%d",ans[i]);
else printf(" %d",ans[i]);
}
printf("\n");
}
int main()
{
int t;scanf("%d",&t);
while(t--)solve();
return 0;
}
HDU 5909 Tree Cutting 动态规划 快速沃尔什变换的更多相关文章
-
hdu 5909 Tree Cutting [树形DP fwt]
hdu 5909 Tree Cutting 题意:一颗无根树,每个点有权值,连通子树的权值为异或和,求异或和为[0,m)的方案数 \(f[i][j]\)表示子树i中经过i的连通子树异或和为j的方案数 ...
-
HDU 5909 Tree Cutting
传送门 题意: 有一棵n个点的无根树,节点依次编号为1到n,其中节点i的权值为vi, 定义一棵树的价值为它所有点的权值的异或和. 现在对于每个[0,m)的整数k,请统计有多少T的非空连通子树的价值等于 ...
-
hdu 5909 Tree Cutting——点分治(树形DP转为序列DP)
题目:http://acm.hdu.edu.cn/showproblem.php?pid=5909 点分治的话,每次要做一次树形DP:但时间应该是 siz*m2 的.可以用 FWT 变成 siz*ml ...
-
HDU 5909 Tree Cutting(FWT+树形DP)
[题目链接] http://acm.hdu.edu.cn/showproblem.php?pid=5909 [题目大意] 给出一棵树,其每棵连通子树的价值为其点权的xor和, 问有多少连通子树的价值为 ...
-
hdu 5909 Tree Cutting —— 点分治
题目:http://acm.hdu.edu.cn/showproblem.php?pid=5909 点分治,每次的 rt 是必选的点: 考虑必须选根的一个连通块,可以DP,决策就是在每个子树中决定选不 ...
-
HDU.5909.Tree Cutting(树形DP FWT/点分治)
题目链接 \(Description\) 给定一棵树,每个点有权值,在\([0,m-1]\)之间.求异或和为\(0,1,...,m-1\)的非空连通块各有多少个. \(n\leq 1000,m\leq ...
-
HDU - 5909 Tree Cutting (树形dp+FWT优化)
题意:树上每个节点有权值,定义一棵树的权值为所有节点权值异或的值.求一棵树中,连通子树值为[0,m)的个数. 分析: 设\(dp[i][j]\)为根为i,值为j的子树的个数. 则\(dp[i][j\o ...
-
【HDU 5909】 Tree Cutting (树形依赖型DP+点分治)
Tree Cutting Problem Description Byteasar has a tree T with n vertices conveniently labeled with 1,2 ...
-
HDU-6881 Tree Cutting (HDU多校D10T5 点分治)
HDU-6881 Tree Cutting 题意 \(n\) 个点的一棵树,要求删除尽量少的点,使得删点之后还是一棵树,并且直径不超过 \(k\),求删除点的数量 分析 补题之前的一些错误想法: 尝试 ...
随机推荐
-
JS组件系列——Bootstrap Table 表格行拖拽
前言:之前一直在研究DDD相关知识,好久没更新JS系列文章了.这两天做了一个简单的业务需求,觉得效果还可以,今天在这里分享给大家,欢迎拍砖~~ 一.业务需求及实现效果 项目涉及到订单模块,那天突然接到 ...
-
USACO翻译:USACO 2014 US Open 三题
USACO 2014 US Open 一.题目概览 中文题目名称 牧场装饰 里程表 牛像展览 英文题目名称 decorate odometer fairphoto 可执行文件名 decorate od ...
-
Caused by: org.hibernate.HibernateException: Connection cannot be null when &#39;hibernate.dialect&#39; not set
docs.jboss.org文档示例代码:(http://docs.jboss.org/hibernate/annotations/3.5/reference/en/html_single/) sta ...
-
Connected_Component Labelling(联通区域标记算法) C++实现
// Connected-Component Labelling.cpp : 定义控制台应用程序的入口点.//如有是使用,请务必注明引用出处网站:http://www.cnblogs.com/Amat ...
-
Java笔记(十六)并发容器
并发容器 一.写时复制的List和Set CopyOnWrite即写时复制,或称写时拷贝,是解决并发问题的一种重要思路. 一)CopyOnWriteArrayList 该类实现了List接口,它的用法 ...
-
calc() --- css3
http://www.w3cplus.com/css3/how-to-use-css3-calc-function.html
-
jquery.lazyload 使用
1.引用js <script src="jquery.js" type="text/javascript"></script> < ...
-
Join, Group Join
Linq的 Join对应SQL中的inner join,当左右两张表有匹配数据时才返回一条记录: Linq的 Group Join对应SQL中的LEFT OUTER JOIN,即使右表中没有匹配,也从 ...
-
Linux 设置默认编辑器(以nano为例)
查看nano地址 which nano output: /usr/bin/nano 设置默认编辑器 nano ~/.bashrc export EDITOR=nano alias vi=/usr/bi ...
-
树状数组优化DP 【模拟赛】删区间
哇,难受得一匹. 看到题的一瞬间竟然只想到了\(n^3\)的区间\(DP\) 一.\(40pts\) 设\(f[i][j]\)代表删去\(i\)到\(j\)这一段区间的最小代价和. 然后直接写普通的区 ...