欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

NOIP 2014 联合权值

程序员文章站 2022-05-22 14:56:10
...

题目链接:

https://www.luogu.org/problemnew/show/P1351

参考洛谷题解:

使用链式前向星储存图。如果使用深度优先搜索的话,是会超时的,如果遍历中间的点,虽然比直接遍历快一点,但是也会超时,画一个有三个顶点一个中心的菊花图,题目就是要求三个顶点两两相乘的和,找规律可得到:结果为三个顶点的和的平方减去三个顶点的平方和,推广到n个顶点也是一样的。由此得出代码:

#include <iostream>      
#include <cstring>
#include <stdio.h>
using namespace std;
typedef long long ll;
const int inf=1e6+7;
struct node
{
    int from,to,next;
}themap[inf];
int head[inf],thevalue[inf],thenow[inf];
int cnt=0;
int themax=-1,theans=0;

void addedge(int u,int v)   //远不如直接在用一个来的好。
{
    themap[cnt].from=u;
    themap[cnt].to=v;
    themap[cnt].next=head[u];
    head[u]=cnt++;

    themap[cnt].from=v;
    themap[cnt].to=u;
    themap[cnt].next=head[v];
    head[v]=cnt++;
}

int main()
{
    int n,u,v;
    memset(head,-1,sizeof(head));
    scanf("%d",&n);
    for(int i=1;i<n;i++)
    {
        scanf("%d %d",&u,&v);
        addedge(u,v);
    }
    for(int i=1;i<=n;i++)
        scanf("%d",&thevalue[i]);
    for(int i=1;i<=n;i++)
    {
        int flag=0;
        ll one=-1,two=-1;       //最大值和次大值。
        ll temp1=0;
        ll temp2=0;
        for(int j=head[i];j!=-1;j=themap[j].next)
        {
            //thenow[flag++]=themap[j].to;
            int now=themap[j].to;       //是其中的值啊.
            if(thevalue[now]>one)
            {
                two=one;
                one=thevalue[now];
            }
            else if(thevalue[now]>two)
                two=thevalue[now];
            temp1+=thevalue[now];
            temp1=temp1%10007;
            temp2+=(thevalue[now]*thevalue[now])%10007;
            temp2=temp2%10007;      
            flag++;
        }
        if(flag==1){}
        else
        {
            if(one*two>themax)
            {
                themax=one*two;                    
            }
            temp1=(temp1*temp1)%10007;
            theans+=(temp1-temp2+10007);        //防止theans成为负的。
            theans=theans%10007;    
        }
    }
    printf("%d %d\n",themax,theans%10007);
    return 0;
}