【题解】联合权值

传送门

解题思路

乍一看还真没有啥思路,只能想到爆搜~ ~(本人过于智障)~~。

看了别的大佬的思路后发现这题无比简单。

首先,因为题目说距离为2,我们可以枚举每一个点i,那个点的两条不同的边所连的点就是距离为2的点。

不过这样还不行,因为需要O(n^3)的时间。于是我们会发现点i所连的点k在点i的连接下能达到的总联合权值就是(点i所有能达到的点点k)-(点k点k)。于是我们可以预处理点i所有能达到的点的值
由i点能达到的最大联合权值等于i能达到的最大的点*另外一个k点。于是我们又可以预处理点i能到达的最大点

代码

#include<bits/stdc++.h>
using namespace std;
struct kkk{
    long long pos;
    long long s;
};
vector<int> G[200005];
long long sum[200005];
long long num[200005];
kkk biggest[200005];
long long ans,maxn;
int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n-1;i++){
        int u,v;
        cin>>u>>v;
        G[u].push_back(v);
        G[v].push_back(u);//建图
    }
    for(int i=1;i<=n;i++){
        cin>>sum[i];
    }
    for(int i=1;i<=n;i++){
        int gsize=G[i].size();
        for(int j=0;j<gsize;j++){
            num[i]+=sum[G[i][j]];//预处理总联合权值
            if(biggest[i].s<sum[G[i][j]]){
                biggest[i].s=sum[G[i][j]];
                biggest[i].pos=G[i][j];
            }//预处理最大联合权值
        }
    }
    for(int i=1;i<=n;i++){
        int gsize=G[i].size();
        for(int j=0;j<gsize;j++){
                    ans+=sum[G[i][j]]%10007*(num[i]-sum[G[i][j]]);
                    ans%=10007;
                    if(biggest[i].pos!=G[i][j]){
                        maxn=max(maxn,biggest[i].s*sum[G[i][j]]);
                    }
        }
    }
    cout<<maxn<<" "<<ans;
    return 0;
} 

本文链接:https://kaispace.com.cn/index.php/archives/567/

如果未注明出处,复制公开后需将注明本博客链接。
打赏作者