code3728 联合权值

一开始暴搜，超时3个点...

后来看了题解：

首先，两个点的距离为2当且仅当它们都与一个点直接相连

反过来说，一个点所有的出边的终点都是互相距离2的(最大值可以依靠这个方法，前向星处理的时候将每个点的最大出点和次大出点存起来，最后过一遍比较乘积)

那么，所有点对的权值和就是每一个点所产生的点对权值和的总和

但此时，如若要对每一个点的出点进行两两配对，每一个点需要O(e^2)(e为该点出度)

只要有一个点有太多的出边就会TLE，此时我们我可以利用乘法分配律

w[i]*w[j1]+w[i]*w[j2]+...+w[i]*w[jn]=w[i]*(w[j1]+...+w[jn])

我们定义一个点的围权和为到该点距离为1的点的权值和

从这个式子中，我们可以看见：i点所产生的权值和，相当于是与i点直接相连的那些点中(j1,j2,j3...)，每个点(j1,j2,j3)的围权和的和，每个围权和减去自己本身，再乘以该点权值

再利用前向星存储，这样时间复杂度会直接降到O(n)

代码：

#include<iostream>

#include<cstdio>

#include<cstring>

#define Size 200005

using namespace std;

int IN[Size][];

struct node{

    int to;

    int next;

}edge[Size*];

int head[Size];

int n;

int w[Size];

long long sum=; int largest=-;

int L[Size][];

long long d[Size];

void check(int a,int b){

    int ww=w[b];

    if(ww>L[a][]){

        L[a][]=L[a][];

        L[a][]=ww;

    }else if(ww>L[a][])L[a][]=ww;

}

int main(){

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

    freopen("3728.in","r",stdin);

    cin>>n;

    int a,b;

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

    for(int i=;i<=n;i++)scanf("%d",w+i);

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

        a=IN[i][]; b=IN[i][];

        edge[i*-].to=b; edge[i*-].next=head[a]; head[a]=*i-;

        check(a,b); d[a]+=w[b];

        edge[i*].to=a; edge[i*].next=head[b]; head[b]=*i;

        check(b,a); d[b]+=w[a];

    }

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

        largest=max(largest,L[i][]*L[i][]);

    }

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

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

            int x=edge[j].to;

            sum+=(w[x]*(d[i]-w[x])%)%;

            sum%=;

        }

    }

    cout<<largest<<' '<<sum<<endl;

    return ;

}