Tree Cutting HDU - 5909

題意：

一個無根樹，n個點，n-1條邊，每個節點有一個權值，一棵樹的權值就是其節點(包含本身及其子節點)的權值的異或和；求價值為[0,m)的樹有多少顆？(所謂的樹其實就是原連通圖的任意子圖)
n<=1000
m<=$2^{10}$

題解：

不難想到樹形dp
設dp[u][i]表示以u節點為根的價值為i的樹的數量
能得到轉移方程：
$dp[u][j?k]=dp[u][j?k]+dp[u][j]?d[v][k]$
u是v的父親節點
不過這個式子直接算會超時,復雜度為$O(n?m?m)$
我們將式子變形：
$dp[u][i]={\sum }_{j?k=i}dp[u][j]?d[v][k]$
這個就長得很像FWT
沒錯，就可以用FWT優化了
每次將dp[u][]和dp[v][]卷起來，并記錄當前節點u為根的答案
優化后復雜度為$O(nmlogm)$

代碼：

#include <bits/stdc++.h> #include <unordered_map> #define debug(a, b) printf("%s = %d\n", a, b); using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<int, int> PII; clock_t startTime, endTime; //Fe~Jozky const ll INF_ll= 1e18; const int INF_int= 0x3f3f3f3f; void read(){}; template <typename _Tp, typename... _Tps> void read(_Tp& x, _Tps&... Ar) {x= 0;char c= getchar();bool flag= 0;while (c < '0' || c > '9')flag|= (c == '-'), c= getchar();while (c >= '0' && c <= '9')x= (x << 3) + (x << 1) + (c ^ 48), c= getchar();if (flag)x= -x;read(Ar...); } template <typename T> inline void write(T x) {if (x < 0) {x= ~(x - 1);putchar('-');}if (x > 9)write(x / 10);putchar(x % 10 + '0'); } void rd_test() { #ifdef ONLINE_JUDGE #elsestartTime = clock ();freopen("data.in", "r", stdin); #endif } void Time_test() { #ifdef ONLINE_JUDGE #elseendTime= clock();printf("\nRun Time:%lfs\n", (double)(endTime - startTime) / CLOCKS_PER_SEC); #endif } const int P=1e9+7; const int mod=1e9+7; const int maxn1=(1<<13); #define int long long int val[1020]; vector<int>vec[2000]; int ans[maxn1]; int tmp[maxn1]; int dp[1020][maxn1]; int n,m; /* 設dp[i][j]:表示以i為根的子樹中異或和為j的數量 */ int qpow(int a,int b){int ans=1;while(b){if(b&1)ans=ans*a%mod;a=a*a%mod;b>>=1;}return ans%mod; } void FWT(int x[],int t1,int t2,int len) {const ll inv2= qpow(2,mod-2);for(int i=1;i<len;i<<=1)for(int j=0;j<len;j+=(i<<1))for(int k=0;k<i;k++){ll p=x[j+k],q=x[i+j+k];if(t1==0) x[i+j+k]=(q+P+t2*p)%P; //orelse if(t1==1) x[j+k]=(p+P+t2*q)%P; //andelse if(t1==2) //xor{x[j+k]=(p+q)%P*(t2<0?inv2:1)%P;x[i+j+k]=(p+P-q)%P*(t2<0?inv2:1)%P;} } } void say(int a[],int len){for(int i=0;i<len;i++){printf("a[%d]=%d\n",i,a[i]);}} void solve(int a[],int b[],int len){ // say(a,len); // say(b,len);FWT(a,2,1,len);FWT(b,2,1,len);for(int i=0;i<len;i++)a[i]=a[i]*b[i]%mod;FWT(a,2,-1,len); } void dfs(int u,int fa){dp[u][val[u]]=1;for(auto v:vec[u]){if(v==fa)continue;dfs(v,u);for(int j=0;j<m;j++){tmp[j]=dp[u][j];}solve(dp[u],dp[v],m);for(int j=0;j<m;j++){dp[u][j]=(tmp[j]+dp[u][j])%mod;}}for(int i=0;i<m;i++){ans[i]=(ans[i]+dp[u][i])%mod;} } signed main() { // rd_test();int t;read(t);while(t--){read(n,m);for(int i=1;i<=n;i++)read(val[i]);for(int i=1;i<n;i++){int u,v;read(u,v);vec[u].push_back(v);vec[v].push_back(u);}memset(dp,0,sizeof dp);memset(ans,0,sizeof ans);dfs(1,1);for(int i=0;i<m;i++){if(i==0)cout<<ans[i];else cout<<" "<<ans[i];}cout<<endl;for(int i=1;i<=n;i++)vec[i].clear();}//Time_test(); } /**/

總結

以上是生活随笔為你收集整理的Tree Cutting HDU - 5909的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。