退役了，但是我发现数据过水

为什么我会重新翻起这题的代码呢？因为我想给同学讲讲树的概念，这题很适合讲解无根树的存储。

下面是我当年的代码。显然我们发现维护前两大点权的方法是错的，但是却通过了目前的数据。

CPP

#include<bits/stdc++.h>
using namespace std;
vector<long long> a[200005];
long long n,w[200005];
long long x,y;
int main()
{
    cin>>n;
    for(long long i=1;i<n;i++)
    {
        scanf("%lld%lld",&x,&y);
        a[x].push_back(y);
        a[y].push_back(x);
    }
    for(long long i=1;i<=n;i++)
        scanf("%lld",&w[i]);
    long long tot=0,best=0;
    for(long long i=1;i<=n;i++)
    {
        long long sum=0,big=0,sec=0;
        for(long long j=0;j<a[i].size();j++)
        {
            sum+=w[a[i][j]];
            if(w[a[i][j]]>=big)
            {
                sec=big;
                big=w[a[i][j]];
            }
        }
        for(long long j=0;j<a[i].size();j++)
            tot=(tot+w[a[i][j]]*(sum-w[a[i][j]]))%10007;
        best=max(best,big*sec);
    }
    cout<<best<<' '<<tot;
    return 0;
}

因此我顺手放一个小测试点：

CPP

答案应为：

CPP

200 604

退役了，但是我发现数据过水

讨论操作

回复

相关推荐

退役了，但是我发现数据过水