洛谷 P1351 （枚举）

题目大意：

给你 n 个节点， n-1 条边的无向联通图。若定义（u，v）表示 u 与 v 点的最短距离，如果（u，v）值为 2 ，则这两个点的点权之积（即 W_u* W_v）称为联合权值,求全图中联合权值的最大值以及联合权值的总和。

分析：

1、由于是 n-1 条边且为无向联通图，很容易判断出该图是个无根树。

2、那我们可以遍历全图中所有节点，然后这些节点的儿子节点的相对距离都是 2 。

3、若 A 节点的两个儿子 a b，他们对答案做贡献的话，那么不可能会有第二个节点也拥有 a b 两个节点作为儿子。所以这样枚举是不会重复的。

4、按理来说，我们需要遍历这个节点的所有儿子节点对，然后依次求和答案。但通过分析可以发现：若有 a b 两个儿子，那么贡献为 2*ab == (ａ + b)² - (a² + b²)；同样若有 3 个儿子 a b c ，则贡献为 2*ab + 2*ac + 2*bc == （a+b+c)² - (a² + b² + c²)。故可以依次统计和与平方和，然后最后处理一下即可。

5、对于判断最大值： A 节点的儿子节点中最大的两个点权之积，即是 A 为父亲节点时的最大联合权值。那么只要取最大父亲节点的最大联合权值即可。

代码如下：

#include<iostream>

#include<algorithm>

#include<string.h>

using namespace std;

#define maxn 200008

typedef long long ll;

const ll mod = ;

int n,cnt;

int head[maxn],in[maxn];

ll a[maxn];

struct Edge{

    int to;

    int next;

}edge[maxn<<];

inline void add(int u,int v){

    edge[++cnt].to=v;

    edge[cnt].next=head[u];

    head[u]=cnt;

    return;

}

int main(){

    scanf("%d",&n);

    int A,B;

    for (int i=; i <= n-; i++) {

        scanf("%d%d",&A,&B);

        add(A,B),add(B,A);

        in[A]++,in[B]++;

    }

    for (int i=; i <= n; i++)  scanf("%lld",&a[i]);

    ll ans=,res=;

    for (int i=; i <= n; i++) {

        if(in[i]<=) continue;

        ll s1=,s2=;

        ll MMax=,mmax=;

        for(int j=head[i];j;j=edge[j].next){

            int v=edge[j].to;

            s1=(s1+a[v])%mod,s2=(s2+a[v]*a[v]%mod)%mod;

            if(a[v]>=MMax){mmax=MMax;MMax=a[v];}

            else if(a[v]>mmax) mmax=a[v];

        }

        ll k = ((s1*s1)%mod-s2+mod)%mod;

        ans=(ans+k)%mod;

        res=max(res,MMax*mmax);

    }

    printf("%lld %lld\n",res,ans);

}

巴特西

洛谷 P1351 （枚举）

最新文章

热门文章