HDU 5909 Tree Cutting 动态规划 快速沃尔什变换

时间:2022-10-02 20:52:42

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 动态规划 快速沃尔什变换的更多相关文章

  1. hdu 5909 Tree Cutting &lbrack;树形DP fwt&rsqb;

    hdu 5909 Tree Cutting 题意:一颗无根树,每个点有权值,连通子树的权值为异或和,求异或和为[0,m)的方案数 \(f[i][j]\)表示子树i中经过i的连通子树异或和为j的方案数 ...

  2. HDU 5909 Tree Cutting

    传送门 题意: 有一棵n个点的无根树,节点依次编号为1到n,其中节点i的权值为vi, 定义一棵树的价值为它所有点的权值的异或和. 现在对于每个[0,m)的整数k,请统计有多少T的非空连通子树的价值等于 ...

  3. hdu 5909 Tree Cutting——点分治(树形DP转为序列DP)

    题目:http://acm.hdu.edu.cn/showproblem.php?pid=5909 点分治的话,每次要做一次树形DP:但时间应该是 siz*m2 的.可以用 FWT 变成 siz*ml ...

  4. HDU 5909 Tree Cutting(FWT&plus;树形DP)

    [题目链接] http://acm.hdu.edu.cn/showproblem.php?pid=5909 [题目大意] 给出一棵树,其每棵连通子树的价值为其点权的xor和, 问有多少连通子树的价值为 ...

  5. hdu 5909 Tree Cutting —— 点分治

    题目:http://acm.hdu.edu.cn/showproblem.php?pid=5909 点分治,每次的 rt 是必选的点: 考虑必须选根的一个连通块,可以DP,决策就是在每个子树中决定选不 ...

  6. HDU&period;5909&period;Tree Cutting&lpar;树形DP FWT&sol;点分治&rpar;

    题目链接 \(Description\) 给定一棵树,每个点有权值,在\([0,m-1]\)之间.求异或和为\(0,1,...,m-1\)的非空连通块各有多少个. \(n\leq 1000,m\leq ...

  7. HDU - 5909 Tree Cutting &lpar;树形dp&plus;FWT优化&rpar;

    题意:树上每个节点有权值,定义一棵树的权值为所有节点权值异或的值.求一棵树中,连通子树值为[0,m)的个数. 分析: 设\(dp[i][j]\)为根为i,值为j的子树的个数. 则\(dp[i][j\o ...

  8. 【HDU 5909】 Tree Cutting (树形依赖型DP&plus;点分治)

    Tree Cutting Problem Description Byteasar has a tree T with n vertices conveniently labeled with 1,2 ...

  9. HDU-6881 Tree Cutting (HDU多校D10T5 点分治)

    HDU-6881 Tree Cutting 题意 \(n\) 个点的一棵树,要求删除尽量少的点,使得删点之后还是一棵树,并且直径不超过 \(k\),求删除点的数量 分析 补题之前的一些错误想法: 尝试 ...

随机推荐

  1. JS组件系列——Bootstrap Table 表格行拖拽

    前言:之前一直在研究DDD相关知识,好久没更新JS系列文章了.这两天做了一个简单的业务需求,觉得效果还可以,今天在这里分享给大家,欢迎拍砖~~ 一.业务需求及实现效果 项目涉及到订单模块,那天突然接到 ...

  2. USACO翻译:USACO 2014 US Open 三题

    USACO 2014 US Open 一.题目概览 中文题目名称 牧场装饰 里程表 牛像展览 英文题目名称 decorate odometer fairphoto 可执行文件名 decorate od ...

  3. Caused by&colon; org&period;hibernate&period;HibernateException&colon; Connection cannot be null when &&num;39&semi;hibernate&period;dialect&&num;39&semi; not set

    docs.jboss.org文档示例代码:(http://docs.jboss.org/hibernate/annotations/3.5/reference/en/html_single/) sta ...

  4. Connected&lowbar;Component Labelling(联通区域标记算法) C&plus;&plus;实现

    // Connected-Component Labelling.cpp : 定义控制台应用程序的入口点.//如有是使用,请务必注明引用出处网站:http://www.cnblogs.com/Amat ...

  5. Java笔记(十六)并发容器

    并发容器 一.写时复制的List和Set CopyOnWrite即写时复制,或称写时拷贝,是解决并发问题的一种重要思路. 一)CopyOnWriteArrayList 该类实现了List接口,它的用法 ...

  6. calc&lpar;&rpar; --- css3

    http://www.w3cplus.com/css3/how-to-use-css3-calc-function.html

  7. jquery&period;lazyload 使用

    1.引用js <script src="jquery.js" type="text/javascript"></script> < ...

  8. Join&comma; Group Join

    Linq的 Join对应SQL中的inner join,当左右两张表有匹配数据时才返回一条记录: Linq的 Group Join对应SQL中的LEFT OUTER JOIN,即使右表中没有匹配,也从 ...

  9. Linux 设置默认编辑器(以nano为例)

    查看nano地址 which nano output: /usr/bin/nano 设置默认编辑器 nano ~/.bashrc export EDITOR=nano alias vi=/usr/bi ...

  10. 树状数组优化DP 【模拟赛】删区间

    哇,难受得一匹. 看到题的一瞬间竟然只想到了\(n^3\)的区间\(DP\) 一.\(40pts\) 设\(f[i][j]\)代表删去\(i\)到\(j\)这一段区间的最小代价和. 然后直接写普通的区 ...