【題目鏈接】:http://hihocoder.com/problemset/problem/1479

【題意】

.

【題解】

首先算出所有節點的權值的和val;
然后如果val%3!=0則直接輸出0；
否則令key = val/3
對于當前節點x;
有兩種情況;
一種是
兩個要刪掉的節點都在同一棵子樹里面;
則某一個子樹里面必須有一個子樹和為key的節點;同時這個點x的子樹和為2*key;->注意這時x節點不能為根節點
另外一種情況就是;
兩個key的節點分別在x的兩棵子樹里面;

【Number Of WA】

1(忘記初始化vector了)

【完整代碼】

#include <bits/stdc++.h> using namespace std; #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 #define LL long long #define rep1(i,a,b) for (int i = a;i <= b;i++) #define rep2(i,a,b) for (int i = a;i >= b;i--) #define mp make_pair #define pb push_back #define fi first #define se second #define ms(x,y) memset(x,y,sizeof x)typedef pair<int,int> pii; typedef pair<LL,LL> pll;const int dx[9] = {0,1,-1,0,0,-1,-1,1,1}; const int dy[9] = {0,0,0,-1,1,-1,1,-1,1}; const double pi = acos(-1.0); const int N = 1e5+100;int n,root,a[N],fa,key; vector <int> son[N]; LL dp1[N],sum[N],ans;void dfs(int x) {dp1[x] = 0;sum[x] = a[x];for (int y:son[x]){dfs(y);sum[x]+=sum[y];ans += dp1[x]*dp1[y];dp1[x]+=dp1[y];}if (x!=root && sum[x]==key*2) ans+=dp1[x];if (sum[x]==key) dp1[x]++; }int main() {//freopen("F:\\rush.txt","r",stdin);ios::sync_with_stdio(false),cin.tie(0);//scanf,puts,printf not useint T;cin >> T;while (T--){ans = 0,key = 0;cin >> n;rep1(i,1,n) son[i].clear();rep1(i,1,n){cin >> a[i] >> fa;if (fa==0)root = i;elseson[fa].pb(i);key+=a[i];}if (key%3!=0){cout << 0 << endl;continue;}key/=3;dfs(root);cout << ans << endl;}return 0; }

轉載于:https://www.cnblogs.com/AWCXV/p/7626391.html

總結

以上是生活随笔為你收集整理的【[Offer收割]编程练习赛9 C】三等分的全部內容，希望文章能夠幫你解決所遇到的問題。

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