hihocoder1479 三等分
生活随笔
收集整理的這篇文章主要介紹了
hihocoder1479 三等分
小編覺得挺不錯的,現在分享給大家,幫大家做個參考.
地址:http://hihocoder.com/problemset/problem/1479
題目:
三等分
時間限制:10000ms 單點時限:1000ms 內存限制:256MB描述
小Hi最近參加了一場比賽,這場比賽中小Hi被要求將一棵樹拆成3份,使得每一份中所有節點的權值和相等。
比賽結束后,小Hi發現雖然大家得到的樹幾乎一模一樣,但是每個人的方法都有所不同。于是小Hi希望知道,對于一棵給定的有根樹,在選取其中2個非根節點并將它們與它們的父親節點分開后,所形成的三棵子樹的節點權值之和能夠兩兩相等的方案有多少種。
兩種方案被看做不同的方案,當且僅當形成方案的2個節點不完全相同。
輸入
每個輸入文件包含多組輸入,在輸入的第一行為一個整數T,表示數據的組數。
每組輸入的第一行為一個整數N,表示給出的這棵樹的節點數。
接下來N行,依次描述結點1~N,其中第i行為兩個整數Vi和Pi,分別描述這個節點的權值和其父親節點的編號。
父親節點編號為0的節點為這棵樹的根節點。
對于30%的數據,滿足3<=N<=100
對于100%的數據,滿足3<=N<=100000, |Vi|<=100, T<=10
輸出
對于每組輸入,輸出一行Ans,表示方案的數量。
樣例輸入思路:哈希+dfs
兩遍dfs,第一遍求出到該點的權值和(sum[x]:權值和),第二遍時計算答案ans。
因為只有三等分,其中一個點已經規定了是根節點,所以只需考慮剩下兩個點(選作根)的情況:
1.兩個點是祖先關系,兩點在同一條鏈上。
2.兩點不在同一條鏈上。
對于這兩種情況,我們可以兩個哈希來解決
對于第一種情況:維護一個map<int,int>fa的哈希,該哈希記錄的是到節點x的所有祖先節點的權值和,則可以三等分時有sum[root]==3*sum[x]?ans+=fa[2*sum[x]]:0;
對于第二種情況:同樣是維護一個哈希map<int,int>hs,該哈希記錄的是除節點的x的祖先節點外已dfs過的節點的權值和,則可以三等分時有sum[root]==3*sum[x]?ans+=hs[sum[x]]:0;
綜上:
if(sum[root]==3*sum[x])
ans+=fa[2*sum[x]]+hs[sum[x]];
另外一種做法,dp!
dp[x][i]:表示到節點x時,合法的i等分的情況有多少種。
然后考慮下子樹合并時的情況就好了。
這種方法可以解決n等分問題,第一種方法不能。
1 #include <bits/stdc++.h> 2 3 using namespace std; 4 5 #define MP make_pair 6 #define PB push_back 7 typedef long long LL; 8 typedef pair<int,int> PII; 9 const double eps=1e-8; 10 const double pi=acos(-1.0); 11 const int K=1e6+7; 12 const int mod=1e9+7; 13 14 int n,v[100005],sum[100005]; 15 vector<int>mp[100005]; 16 map<int,int>hs,fa; 17 LL ans; 18 void dfs1(int x) 19 { 20 sum[x]=v[x]; 21 for(int i=0;i<mp[x].size();i++) 22 dfs1(mp[x][i]),sum[x]+=sum[mp[x][i]]; 23 } 24 void dfs2(int x,int f) 25 { 26 if(x!=f&&sum[f]==3*sum[x]) ans+=fa[sum[x]*2]+hs[sum[x]]; 27 if(x!=f)fa[sum[x]]++; 28 for(int i=0;i<mp[x].size();i++) 29 { 30 int u=mp[x][i]; 31 dfs2(u,f),hs[sum[u]]++; 32 } 33 if(x!=f)fa[sum[x]]--; 34 } 35 int main(void) 36 { 37 int t;cin>>t; 38 while(t--) 39 { 40 ans=0; 41 memset(sum,0,sizeof(sum)); 42 hs.clear(),fa.clear(); 43 memset(mp,0,sizeof(mp)); 44 cin>>n; 45 for(int i=1,x;i<=n;i++) 46 scanf("%d%d",&v[i],&x),mp[x].PB(i); 47 dfs1(mp[0][0]); 48 if(sum[mp[0][0]]%3==0) 49 dfs2(mp[0][0],mp[0][0]); 50 cout<<ans<<endl; 51 } 52 return 0; 53 } 54 /* 55 123 56 13 57 0 0 58 -1 1 59 1 2 60 -1 3 61 1 4 62 -1 5 63 1 6 64 -1 1 65 1 8 66 -1 9 67 1 10 68 -1 11 69 1 12 70 7 71 0 0 72 0 1 73 0 2 74 0 3 75 0 1 76 0 5 77 0 6 78 5 79 0 0 80 0 1 81 0 1 82 0 1 83 0 1 84 9 85 0 0 86 0 1 87 0 2 88 0 1 89 0 4 90 0 1 91 0 6 92 0 1 93 0 8 94 */
?
?轉載于:https://www.cnblogs.com/weeping/p/6541520.html
總結
以上是生活随笔為你收集整理的hihocoder1479 三等分的全部內容,希望文章能夠幫你解決所遇到的問題。
- 上一篇: iOS之Block总结以及内存管理
- 下一篇: 031 广播变量与累加器