首页 > 代码库 > 【HDU 5909】 Tree Cutting (树形依赖型DP+点分治)
【HDU 5909】 Tree Cutting (树形依赖型DP+点分治)
Tree Cutting
Problem DescriptionByteasar 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.
InputThe 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.
OutputFor 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 Input24 42 0 1 31 21 31 44 40 1 3 11 21 31 4
Sample Output3 3 2 32 4 2 3
SourceBestCoder Round #88
【题意】
Byteasar有一棵nn个点的无根树,节点依次编号为11到nn,其中节点ii的权值为v_iv?i??。定义一棵树的价值为它所有点的权值的异或和。现在对于每个[0,m)[0,m)的整数kk,请统计有多少TT的非空连通子树的价值等于kk。一棵树TT的连通子树就是它的一个连通子图,并且这个图也是一棵树。
【分析】
先放个题解:
本题有两种可以AC的算法。
算法1:
取一个根,将这棵树转化为有根树,并假设根必须要选,那么对于一个点来说,如果它选了,它的父亲就必须选。
求出dfs序,设f[i][j]f[i][j]表示考虑了dfs序的前ii项,目前连通块的异或和为jj的方案数。
如果ii是一个左括号,那么把ff传给儿子,并强制选择儿子;如果ii是个右括号,那么这个子树既可以选又可以不选,累加即可。
如果根必然不选,那么可以去掉这个根,变成若干棵树的子问题,这显然是点分治的形式,取重心作为根即可。
时间复杂度O(nm\log n)O(nmlogn)。
算法2:
取11为根,设sum[x]sum[x]表示xx子树的异或和,假如选择的连通块的根是xx,那么要在xx子树里选择若干不相交的子树舍弃掉。
设f[i][j]f[i][j]表示ii的子树里舍弃了jj的方案数,转移是个异或卷积的形式,可以用FWT加速计算。
时间复杂度O(nm\log m)O(nmlogm)。
题解还是通俗易懂的,然而FWT是啥,表示不会。
树形依赖还会一点,所以就打了第一种解法。
然而之前没有打过点分治哦,原来重心还挺好用的....
每次分治的时候都要找重心,那么深度就不会超过logn。。
代码如下:
1 #include<cstdio> 2 #include<cstdlib> 3 #include<cstring> 4 #include<iostream> 5 #include<algorithm> 6 #include<queue> 7 #include<cmath> 8 using namespace std; 9 #define INF 0xfffffff10 #define Mod 100000000711 #define Maxn 110012 13 int v[Maxn],first[Maxn];14 15 struct node16 {17 int x,y,next;18 }t[2*Maxn];int len;19 20 void ins(int x,int y)21 {22 t[++len].x=x;t[len].y=y;23 t[len].next=first[x];first[x]=len;24 }25 26 int mymax(int x,int y) {return x>y?x:y;}27 28 int sm[Maxn],mx[Maxn],ms,nm;29 int n,m;30 bool q[Maxn];31 32 void dfs(int x,int f,int sn)33 {34 int h=0;35 mx[x]=0;sm[x]=1;36 for(int i=first[x];i;i=t[i].next) if(t[i].y!=f&&q[t[i].y])37 {38 dfs(t[i].y,x,sn);39 sm[x]+=sm[t[i].y];40 mx[x]=mymax(mx[x],sm[t[i].y]);41 }42 if(sm[x]!=h) mx[x]=mymax(mx[x],sn-sm[x]);43 if(mx[x]<mx[ms]) ms=x;44 }45 46 int ans[Maxn],g[Maxn][Maxn];47 void get_ans(int x,int f)48 {49 for(int i=first[x];i;i=t[i].next) if(t[i].y!=f&&q[t[i].y])50 {51 int y=t[i].y;52 for(int j=0;j<=nm;j++) g[y][j]=0;53 for(int j=0;j<=nm;j++) g[y][j^v[y]]=(g[y][j^v[y]]+g[x][j])%Mod;54 get_ans(y,x);55 for(int j=0;j<=nm;j++) g[x][j]=(g[x][j]+g[y][j])%Mod;56 }57 }58 59 void ffind(int x,int f)60 {61 for(int i=0;i<=nm;i++) g[x][i]=0;62 g[x][v[x]]=1;63 get_ans(x,f);q[x]=0;64 for(int i=0;i<m;i++) ans[i]=(ans[i]+g[x][i])%Mod;65 for(int i=first[x];i;i=t[i].next) if(t[i].y!=f&&q[t[i].y])66 {67 ms=0;68 dfs(t[i].y,0,sm[t[i].y]);69 ffind(ms,0);70 }71 }72 73 int main()74 {75 int T;76 scanf("%d",&T);77 while(T--)78 {79 scanf("%d%d",&n,&m);nm=0;80 memset(first,0,sizeof(first));81 len=0;82 for(int i=1;i<=n;i++) {scanf("%d",&v[i]);nm|=v[i];}83 for(int i=1;i<n;i++)84 {85 int x,y;86 scanf("%d%d",&x,&y);87 ins(x,y);ins(y,x);88 }89 mx[0]=INF;ms=0;90 memset(q,1,sizeof(q));91 dfs(1,0,n);92 memset(g,0,sizeof(g));93 memset(ans,0,sizeof(ans));94 ffind(ms,0);95 for(int i=0;i<m-1;i++) printf("%d ",ans[i]);96 printf("%d\n",ans[m-1]);97 }98 return 0;99 }
无数次傻逼加搞死自己,,233,,,
照例总结:
树形依赖型问题:
最好尽量让 泛化物品合普通物品,或者泛化物品和泛化物品的普通和(就是直接取最值的合 法)
不然 泛化物品和泛化物品的 复杂 的 合 要v^2,很慢的!!
有几种题型,如果v=n(就是说容量就是选取的点数,且选取的点数和答案相关)
可以打成n^2,计算子树答案的时候只for到字数大小即可。
这样打的话是表示子树的答案,所以不一定选原树的根的。
另一种v>>n,
如果根一定选,我们可以用dfs序dp,f[x]表示要选x这个点,并且x到根的路径的点都一定选。
中间是泛化物品合普通物品+泛化物品min|max泛化物品,总时间是nv。
那么不一定选根呢?(即选择一个联通块即可),就用点分治,算完根一定选之后,把根删掉,变成多个子树问题
每次选重心作为根可以优化到分治logn次
这一题就是这样做,总时间是nvlogn
2016-10-07 13:07:14
【HDU 5909】 Tree Cutting (树形依赖型DP+点分治)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。