【NOIP2014】联合权值 树上dp

题目描述 Description

无向连通图G 有n 个点，n - 1 条边。点从1 到n 依次编号，编号为 i 的点的权值为W i   ，每条边的长度均为1 。图上两点( u ,  v ) 的距离定义为u 点到v 点的最短距离。对于图G 上的点对( u, v) ，若它们的距离为2 ，则它们之间会产生Wu
×Wv 的联合权值。
请问图G 上所有可产生联合权值的有序点对中，联合权值最大的是多少？所有联合权值之和是多少？

输入输出格式 Input/output

输入格式：
输入文件名为link .in。
第一行包含1 个整数n 。
接下来n - 1 行，每行包含 2 个用空格隔开的正整数u 、v ，表示编号为 u 和编号为v 的点之间有边相连。
最后1 行，包含 n 个正整数，每两个正整数之间用一个空格隔开，其中第 i 个整数表示图G 上编号为i 的点的权值为W i 。
输出格式：
输出文件名为link .out 。
输出共1 行，包含2 个整数，之间用一个空格隔开，依次为图G 上联合权值的最大值
和所有联合权值之和。由于所有联合权值之和可能很大，输出它时要对10007 取余。

输入样例：

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

输出样例：

20 74

 

思路：

 

一般的做法，可能采用floyd这种鬼畜的最短路来慢慢搞，当然这样做是会完美T掉的！

所以我们要采取机智的方法，距离为2的话，我们就枚举中间的点，这样，他的任意两个儿子的距离就是2~(≧▽≦)/~啦啦啦

第一问答案，就是枚举每个点的第一大和第二大的儿子，相乘求最大就好

第二问答案我们得化简一下，比如有a有三个儿子，那么答案就是cb,cd,bd，然后稍微推广一下，就知道答案是 ((∑儿子)^2-∑(儿子)^2)/2，然后利用前缀和思想维护一下，就好啦

~(≧▽≦)/~啦啦啦

 

代码：

//qscqesze
#include <cstdio>
#include <cmath>
#include <cstring>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <set>
#include <vector>
#include <sstream>
#include <queue>
#include <typeinfo>
#include <fstream>
#include <map>
typedef long long ll;
using namespace std;
//freopen("D.in","r",stdin);
//freopen("D.out","w",stdout);
#define sspeed ios_base::sync_with_stdio(0);cin.tie(0)
#define maxn 200001
#define mod 10007
#define eps 1e-9
const int inf=0x7fffffff;   //无限大
//**************************************************************************************

vector<int> point[maxn];
void add_edge(int a,int b)
{
    point[a].push_back(b);
    point[b].push_back(a);
}
ll h[maxn];
int main()
{
    int n,a,b;
    scanf("%d",&n);
    for(int i=0;i<n-1;i++)
    {
        scanf("%d%d",&a,&b);
        add_edge(a,b);
    }
    for(int i=1;i<=n;i++)
        scanf("%d",&h[i]);
    ll ans1=0,ans2=0;
    for(int i=1;i<=n;i++)
    {
        ll max_num=0,sum=0;
        for(int j=0;j<point[i].size();j++)
        {
            int now=point[i][j];
            ans1=max(ans1,max_num*h[now]);
            ans2=(ans2+sum*h[now]+mod)%mod;
            max_num=max(max_num,h[now]);
            sum+=h[now];
        }
    }
    cout<<ans1<<" "<<(ans2*2+mod)%mod<<endl;
}