题目描述

blablabla

样例

#include<bits/stdc++.h>
using namespace std;
//最大节点数量为1e6
const int N = 1e6+10, M = N;
int h[N];//存储(父)节点连接的第一条边
int ne[M];//重要：存储的是连接同一父节点的边中的下一个节点
int e[M];//存储的是边连接的另一个节点(子节点)
int w[N];
int idx;
int sum;
int n;
vector<int> ans;
void add(int a,int b){
    e[idx] = b;
    //有点像头插法链表
    ne[idx] = h[a];
    h[a] = idx++;
}
int dfs(int u){
    int res = w[u];
    for(int i=h[u];i!=-1;i=ne[i]){
        int j = e[i];//i作为父，j作为子
        int s = dfs(j);
        if(s == sum / 3)
            ans.push_back(j);
        else
            res += s;
    }   
    return res;
}
int main(){
    cin>>n;
    memset(h,-1,sizeof(h));
    int root;
    for(int i=1;i<=n;i++){
        int f;
        cin>>f>>w[i];
        if(f){
            add(f,i);
        }
        else
            root = i;
        sum += w[i];
    }
    if(sum % 3 )
        puts("-1");
    else{
        dfs(root);
        if(ans.size() < 2)
            puts("-1");
        else
            cout<<ans[0]<<" "<<ans[1];
    }
    return 0;
}

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla