求大神看看，怎么改都是60

include

using namespace std; const int maxn = 1e5 + 5; struct note { int to, nex; } a[maxn * 2]; int fir[maxn], val[maxn], len, num1[maxn], num2[maxn], sum[maxn]; int n, s, ans2, ans1; void add(int t1,int t2) { a[len]=note{t2,fir[t1]}; fir[t1]=len++; }

void dfs(int i,int fa) //sum为节点所有子孙节点的总和，num1是子孙和为s的个数 { sum[i]=val[i]; for (int q=fir[i];q+1;q=a[q].nex) { int v=a[q].to; if (v==fa) continue; dfs(v,i); sum[i]+=sum[v]; num1[i]+=num1[v]; } if (sum[i]==s) { num1[i]++; } }

void ddfs(int i,int fa) //num2是祖先节点和为s的个数 { if (sum[i]==s) num2[i]++; for (int q=fir[i];q+1;q=a[q].nex) { int v=a[q].to; if (v==fa) continue; num2[v]+=num2[i]; ddfs(v,i); } } int main() { int T;

scanf("%d", &T);

while (T--)
{
    memset(fir, -1, sizeof fir);
    memset(val, 0, sizeof val);
    len = 0;
    memset(num1, 0, sizeof num1);
    memset(num2, 0, sizeof num2);
    memset(sum, 0, sizeof sum);
    s=0;
    scanf("%d", &n);

    int t1, t2;
    for (int q = 1; q <= n; q++)
    {
        scanf("%d%d", &t1, &t2);
        val[q] = t1;
        s+=t1;
        add(t2, q);
        add(q, t2);
    }

    if (s%3!=0) 
        printf("0\n");
    else 
    {
        s/=3;
        ans1=0,ans2=0;
        dfs(0,0);
        ddfs(0,0);

        for (int q=1;q<=n;q++)
        {
            if (sum[q]==s) ans1+=num1[0]-num1[q]-num2[q]+1;
            if (sum[q]==2*s){
                ans2+=num1[q];
            }
        }
        printf("%d\n",ans1/2+ans2);
    }


}

return 0;

}

那位能帮忙看看，是什么地方有问题么？一直WA……

#include <iostream>
#include <vector>

using namespace std;

struct TreeNode
{
    TreeNode() :Val(0), M1(0) {}
    int64_t Val;    // value for tree
    int64_t M1; // all 1/3 son node (include itself) 
    vector<int64_t> Next;
};

class Worker
{
public:
    void Work()
    {
        cin >> N;
        mTree.resize(N + 1);
        int64_t p = 0;
        mSum = 0;
        for (int64_t i = 1; i <= N; ++i)
        {
            cin >> mTree[i].Val >> p;
            mTree[p].Next.emplace_back(i);
            mSum += mTree[i].Val;
        }
        if (mSum % 3 == 0)
        {
            mM = mSum / 3;
            auto & node = mTree[1];
            for (auto & i : node.Next)
            {
                DFS(i);
                node.Val += mTree[i].Val;
                node.M1 += mTree[i].M1;
            }
            mAns1 = mAns2 = 0;
            for (auto & i : node.Next)
            {
                DFS(i, 0);
            }
            cout << mAns1 / 2 + mAns2 << endl;
        }
        else
        {
            cout << 0 << endl;
        }

    }

private:
    int64_t N;
    int64_t mSum;
    int64_t mM;
    int64_t mAns1, mAns2;
    vector<TreeNode> mTree;

    void DFS(const int64_t & n)
    {
        auto & node = mTree[n];
        for (auto & i : node.Next)
        {
            DFS(i);
            node.Val += mTree[i].Val;
            node.M1 += mTree[i].M1;
        }
        if (node.Val == mM)
            ++node.M1;
    }

    void DFS(const int64_t & n, const int64_t & pre)
    {
        auto & node = mTree[n];
        if (node.Val == 2 * mM)
        {
            mAns2 += node.M1 - (node.Val == mM ? 1 : 0);
        }
        if (node.Val == mM)
        {
            mAns1 += mTree[1].M1 - node.M1 - pre;
        }
        for (auto & i : node.Next)
        {
            DFS(i, pre + (node.Val == mM ? 1 : 0));
        }
    }

};

int main()
{
    uint32_t T = 0;
    cin >> T;
    do
    {
        Worker w;
        w.Work();
    } while (--T > 0);
    return 0;
}

我的做法是这样的

从根节点往下遍历一次，只有子节点都遍历完了才能算出父节点的权值和。也就是进入这个当前节点的时候，之前统计出来权值和为sum/3的节点，通通都不会是当前节点的祖先节点或者子孙节点

用一个全局变量n3统计当前权值和为s3=sum/3的节点的数量

进入一个节点的时候，用一个局部变量t3记录下当前的n3的值，当遍历完所有子节点之后 如果权值和为s3*2时，ans+=n3-t3； 如果权值和为s3时，ans+=t3，并且n3++；

这样遍历完整棵树之后，输入ans就是答案了

请帮忙看看有什么错，跟分析的计算稍有点不同，60%...

#include <bits/stdc++.h>
using namespace std;

constexpr int MOD = 1e9 + 7;
constexpr int MAXN = 2e5 + 1;

using ll = long long;

int N, M, K;

struct Node {
    int tot = 0;  // 权值
    vector<Node* > children;
} nodes[MAXN];

void GenTot(Node* root) {
    for (Node * child : root->children) {
        GenTot(child);
        root->tot += child->tot;
    }
}

int dfs(Node* root, ll& ans) {
    int cnt = 0;  // 子节点等于K的个数
    vector<int> rets;
    for (Node* child : root->children) {
        int t = dfs(child, ans);
        rets.emplace_back(t);
        cnt += t;
    }
    ll tmp = 0;
    // 比如rets = {1, 2, 3, 3}， 下面的三行相当于ans += 1*2 + 1*3 + 1*4 + 2*3 + 2*4 + 3*4
    for (int ret : rets)
        tmp += 1LL * (cnt - ret) * ret;  // 计算题目分析中的ans1
    ans += tmp / 2;
    if (root->tot == 2 * K && root != &nodes[0]) {
        ans += cnt;  // 计算题目分析中的ans2
    }
    return cnt + (root->tot == K ? 1 : 0);
}

ll Solution() {
    GenTot(&nodes[0]);
    int tot = nodes[0].tot;
    if (tot % 3 != 0)
        return 0;
    ll ans = 0;
    K = tot / 3;
    dfs(&nodes[0], ans);
    return ans;
}

int main() {
    freopen("in.txt", "r", stdin);
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    int T;
    int v, p;
    while (cin >> T) {
        while (T--) {
            cin >> N;
            for (int i = 0; i <= N; i++) {
                nodes[i].tot = 0;
                nodes[i].children.clear();
            }

            for (int i = 1; i <= N; i++) {
                cin >> v >> p;
                nodes[i].tot = v;
                nodes[p].children.emplace_back(&nodes[i]);
            }
            cout << Solution() << '\n';
        }
    }
    return 0;
}