vijos1906:联合权值

描述

无向连通图 G 有 n 个点，n-1 条边。点从 1 到 n 依次编号，编号为 i 的点的权值为 WiWi，每条边的长度均为 1。图上两点(u, v)的距离定义为 u 点到 v 点的最短距离。对于图 G 上的点对(u, v)，若它们的距离为 2，则它们之间会产生WuWu×WvWv的联合权值。

请问图 G 上所有可产生联合权值的有序点对中，联合权值最大的是多少？所有联合权值之和是多少？

格式

输入格式

第一行包含 1 个整数 n。

接下来 n-1 行，每行包含 2 个用空格隔开的正整数 u、v，表示编号为 u 和编号为 v 的点之间有边相连。

最后 1 行，包含 n 个正整数，每两个正整数之间用一个空格隔开，其中第 i 个整数表示图 G 上编号为 i 的点的权值为WiWi。

输出格式

输出共 1 行，包含 2 个整数，之间用一个空格隔开，依次为图 G 上联合权值的最大值和所有联合权值之和。由于所有联合权值之和可能很大，输出它时要对10007取余。

样例输入：

5
1 2
2 3
3 4
4 5
1 5 2 3 10

样例输出:

20 74

思路：距离为2的两个结点为具有相同父亲结点的兄弟结点。依次遍历每个结点子节点，求权值之和sum以及各个结点权值平方值和self。该父结点的所有儿子结点产生的权值之和为sum*sum-self。联合权值最大值为遍历各个父节点儿子结点权值的最大值与次大值。求积再与全局变量比较。

#include <iostream>

#include <string.h>

#include <algorithm>

using namespace std;

typedef long long ll;

const int MAXN=;

const int MOD=;

struct Edge{

    int to,net;

}es[MAXN+MAXN];

int n,w[MAXN];

int head[MAXN],tot;

void addedge(int u,int v)

{

    es[tot].to=v;

    es[tot].net=head[u];

    head[u]=tot++;

}

ll mx,res;

void solve()

{

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

    {

        ll mx1=,mx2=;

        ll sum=,self=;

        for(int j=head[i];j!=-;j=es[j].net)

        {

            int  v=es[j].to;

            if(w[v]>=mx1)

            {

                mx2=mx1;

                mx1=w[v];

            }

            else if(w[v]>mx2)

            {

                mx2=w[v];

            }

            sum+=w[v];

            self+=(w[v]*w[v]);

        }

        mx=max(mx,mx1*mx2);

        res+=(sum*sum);

        res-=self;

        res%=MOD;

    }

}

int main()

{

    memset(head,-,sizeof(head));

    cin>>n;

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

    {

        int u,v;

        cin>>u>>v;

        addedge(u,v);

        addedge(v,u);

    }

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

    {

        cin>>w[i];

    }

    solve();

    cout<<mx<<" "<<res<<endl;

    return ;

}

巴特西

vijos1906:联合权值

描述

格式

输入格式

输出格式

最新文章

热门文章