鏈接：https://www.nowcoder.com/acm/contest/57/F

時間限制：C/C++ 2秒，其他語言4秒

空間限制：C/C++ 262144K，其他語言524288K
64bit IO Format: %lld

題目描

白云有一棵n個結點的樹，以1號結點為根，這棵樹的每個結點有一個權值val_i 定義一個連通塊的喜愛度為塊內所有結點權值的乘積。 白兔有很多疑問，每個疑問有兩個參數k,s，表示詢問所有經過點k的大小為s的連通塊的喜愛度之和。
白云會定期對樹做一些修改。

輸入描述:

第一行1個整數n,Q，表示樹的結點個數和事件個數。
第二行n個整數表示val _{1 ... n}。
第三行n-1個整數表示2...n號結點的父親。 接下來Q行，第一個數為op∈{0,1}， 如果op=0表示白云要對某個結點的權值進行修改，接下來兩個數k,c表示把結點k的權值修改為c。 如果op=1表示白兔的疑問，接下來兩個數k,s。

輸出描述:

?對于op=1，每行一個數表示答案。答案對1e9+7 取模。 示例1

輸入

15 15 6 4 8 6 8 9 10 9 2 9 8 3 3 6 2 1 1 1 3 1 3 6 5 3 10 9 7 9 13 1 13 8 1 2 4 1 12 8 1 11 2 0 2 9 0 11 4 1 3 6 0 4 5 1 13 7 1 8 2 1 7 6 1 7 8 0 5 5 0 1 7 1 1 6

輸出

128592000 11304 35520768 72 10402608 16325280 81 6030720 359079840 8686888

備注:

結點k的父親為1...k-1的一個均勻隨機整數。 val_i∈[1,10⁹+7),s≤10,n,Q≤10^5 題解：

//

1 #include <bits/stdc++.h> 2 #define mst(a,b) memset((a),(b), sizeof a) 3 #define lowbit(a) ((a)&(-a)) 4 #define IOS ios::sync_with_stdio(0);cin.tie(0); 5 #define MP make_pair 6 using namespace std; 7 typedef long long ll; 8 typedef pair<int,int> pii; 9 const int mod=1e9+7; 10 const int maxn=1e5+10; 11 ll dp[maxn][11]; 12 int val[maxn],fa[maxn]; 13 vector<int>son[maxn]; 14 int qpow(ll a,int b){ 15 ll res=1; 16 while(b){ 17 if(b&1)res=res*a%mod; 18 b>>=1; 19 a=a*a%mod; 20 } 21 return res; 22 } 23 void add(int a,int b){ 24 for(int i=10;i;--i) 25 for(int j=1;j<i;++j) 26 dp[a][i]=(dp[a][i]+dp[b][j]*dp[a][i-j])%mod; 27 28 } 29 void del(int a,int b){ 30 for(int i=1;i<=10;++i) 31 for(int j=1;j<i;++j) 32 dp[a][i]=(dp[a][i] - dp[b][j]*dp[a][i-j])%mod; 33 } 34 void dfs(int pos){ 35 dp[pos][0]=1;dp[pos][1]=val[pos]; 36 for(int i=0;i<son[pos].size();++i){ 37 int to=son[pos][i]; 38 dfs(to); 39 add(pos,to); 40 } 41 } 42 void update_1(int pos){ 43 if(pos==1)return; 44 update_1(fa[pos]); 45 del(fa[pos],pos); 46 } 47 void update_2(int pos){ 48 if(pos==1)return; 49 add(fa[pos],pos); 50 update_2(fa[pos]); 51 } 52 void update(int k,int c){ 53 update_1(k); 54 int cc=qpow(val[k],mod-2); 55 for(int i=1;i<=10;++i) 56 dp[k][i]=dp[k][i]*cc%mod*c%mod; 57 val[k]=c; 58 update_2(k); 59 } 60 ll dd[2][11]; 61 int now; 62 void qq(int pos,int s){ 63 if(pos!=1)qq(fa[pos],pos); 64 now^=1; 65 memcpy(dd[now],dp[pos],sizeof dp[pos]); 66 for(int i=1;i<=10;++i) 67 for(int j=1;j<i;++j) 68 dd[now][i]=(dd[now][i] - dp[s][j]*dd[now][i-j])%mod; 69 if(pos!=1){ 70 for(int i=10;i;--i) 71 for(int j=1;j<i;++j) 72 dd[now][i]=(dd[now][i]+dd[now^1][j]*dd[now][i-j])%mod; 73 } 74 } 75 int query(int k,int s){ 76 if(k==1)return (dp[k][s]+mod)%mod; 77 int f=fa[k]; 78 qq(f,k); 79 ll ret=0; 80 for(int i=0;i<s;++i) 81 ret=(ret+dd[now][i]*dp[k][s-i])%mod; 82 return (ret+mod)%mod; 83 } 84 int main(){ 85 #ifdef local 86 freopen("in.txt","r",stdin); 87 //freopen("out.txt","w",stdout); 88 #endif 89 int n,q;scanf("%d%d",&n,&q); 90 for(int i=1;i<=n;++i)scanf("%d",&val[i]); 91 for(int i=2;i<=n;++i){ 92 scanf("%d",&fa[i]); 93 son[fa[i]].push_back(i); 94 } 95 dfs(1); 96 while(q--){ 97 int op,a,b;scanf("%d%d%d",&op,&a,&b); 98 if(op)printf("%d\n",query(a,b)); 99 else update(a,b); 100 } 101 return 0; 102 }

首先是隨機樹的樹高是logn這點是不知道的，所以看到題就是蒙圈的，這點是學到了

然后在碼的過程中update那個函數，里面對于k點dp值的更新我一開始是這樣的

　　 for(int i=1;i<=10;++i){dp[k][i]=(dp[k][i]-val[k]*dp[k][i-1])%mod;dp[k][i]=(dp[k][i]+mod)%mod;}val[k]=c;for(int i=10;i;--i){dp[k][i]=(dp[k][i]+dp[k][i-1]*val[k])%mod;}

錯的很離譜，引以為鑒

?

轉載于:https://www.cnblogs.com/bibibi/p/8454490.html

總結

以上是生活随笔為你收集整理的wannalfy 挑战赛8 F 白云的树（树形dp）的全部內容，希望文章能夠幫你解決所遇到的問題。

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