我是弱渣，虽然有大神题解，呵呵，看不懂。于是自己写了。

首先是最容易想到的。用前向星，邻接表来存图。然后枚举所有产生的点。嗯，时间复杂度会被卡成N^2,然后只能60分

优化下。比如1和3和3和1，可以提前计算，算1和3的时候乘2.然后3和1就不算了。只要判断i<J再算就可以优化。大概70分。所以这个思路本身就有不能拿到满分。

仔细分析，考虑这样有个点。A，所有和他相邻的点为B,C,D等等。那么这些点都可以两两产生联合权值。不难推出其中公式。

拿3个点的情况来举例。A连着B,C,D3个点，记这3个点的W为b，c，d。那么总的权值是bc+bd+cb+cd+db+dc=2bc+2bd+2cd。这是n^2时候的枚举算法。我们处理下。看到这个式子想到什么？没错，完全平方。就是（a+b）^2=a^2+b^2+2ab.

同理。把这个式子一般化。不难知道。2bc+2bd+2cd=（b+c+d)^2-b^2-c^2-d^2.这样的话，在N的复杂度就能瞬间得到一个顶点答案。因此只要枚举所有点即可。

至于最大值只要把这个点相邻的点最大值W和次大值W找出来就是该点能出来的最大值。跟max比较。

这样的话只要枚举所有节点就可以得出答案。时间复杂度只有N，轻松AC。

附上代码，star代表前向星（自行百度）一种存图方式。

###block code
program P1906;
const maxn=400001;
var ans,max,sum2,sum:int64;
i,j,n,now,k,num1,num2:longint;
s,w:array[1..200000] of longint;
first,last:array[1..maxn] of longint;
data,new:array[1..maxn,1..2] of longint;
procedure star;//构造计数排序优化的前向星。自己百度百科不谢。
begin
for i:=1 to n-1 do
begin
read(data[i,1],data[i,2]); inc(s[data[i,1]]);
data[n-1+i,1]:=data[i,2]; data[n-1+i,2]:=data[i,1]; inc(s[data[i,2]]);
end;
first[1]:=1;
for i:=2 to n do begin first[i]:=first[i-1]+s[i-1]; last[i]:=first[i]-1; end;
for i:=1 to (n-1) shl 1 do
begin
inc(last[data[i,1]]); now:=last[data[i,1]]; new[now,1]:=data[i,1]; new[now,2]:=data[i,2];
end;

end;
begin //main
fillchar(data,sizeof(data),0); ans:=0; max:=0; fillchar(last,sizeof(last),0);
fillchar(s,sizeof(s),0); fillchar(first,sizeof(first),0);
read(n);
star;
for i:=1 to n do read(w[i]); //以上是读入

for i:=1 to n do //枚举所有点
begin
sum:=0; num1:=0; num2:=0; sum2:=0;
//sum表示（a+b+c+....）。sum2是a^2+b^2+.... 自己看上面题解。通过sum和sum2可以得到总的权值
//num1是该点最大的W，2是次W。
if s[i]>1 then //1个点出度大于2才能有权值产生。枚举所有出度大于2的点

begin
for j:=first[i] to last[i] do //枚举所有跟i节点相邻的点
begin
sum:=w[new[j,2]]+sum; sum2:=w[new[j,2]]*w[new[j,2]]+sum2; //计算sum
if w[new[j,2]]>num2 then //寻找最大值和次大值
if w[new[j,2]]>num1 then
begin
num2:=num1; num1:=w[new[j,2]];
end
else
begin
num2:=w[new[j,2]];
end;
end;
end;
ans:=((ans+(sum*sum)-sum2) mod 10007); //ans是最终总答案。该i节点总权值为sum*sum-sum2
if num1*num2>max then //计算该节点能产生的最大值。如果比max大就保留
max:=num1*num2;
end;
ans:=ans mod 10007; //保险
write(max,' ',ans); //max最大值。ans总答案、
end. //完美解决

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<queue>
#include<string>
#include<map>
#include<cstring>
#include<vector>
#define inf 1e9
#define ll long long
#define For(i,j,k) for(ll i=j;i<=k;i++)
#define Dow(i,j,k) for(ll i=k;i>=j;i--)
using namespace std;
int v[1000001],poi[1000001],nxt[1000001],f[1000001],cnt,n,ma,ans;
inline void add(int x,int y)
{
    poi[++cnt]=y;nxt[cnt]=f[x];f[x]=cnt;
}
void doit(int x)
{
    int sum=0;
    int maxn=0,s_maxn=0;
    for(int i=f[x];i;i=nxt[i])
    {
        int p=poi[i];
        if(v[p]>maxn)   s_maxn=maxn,maxn=v[p];
        else if(v[p]>s_maxn)    s_maxn=v[p];
        ans+=v[p]*sum;
        sum+=v[p];
        ans%=10007;sum%=10007;
    }
    ma=max(ma,maxn*s_maxn);
}
int main()
{
    scanf("%d",&n);
    For(i,1,n-1)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        add(x,y);add(y,x);
    }
    For(i,1,n)  scanf("%d",&v[i]);
    For(i,1,n)  doit(i);
    printf("%d %d",ma%10007,ans*2%10007);
}

由于前向星好难，本蒟蒻不会写
所以只能用vector了QAQ
不一定要开long long也能过的
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <vector>
#include <queue>
#define N 200100
const int k=10007;
using namespace std;
vector<int>a[N];
int w[N];
int n,x,y,v,p,q,l,maxn,ans;
int max1,max2;
int main()
{
scanf("%d",&n);
for(int i=1;i<=n-1;i++)
{
int x,y;
scanf("%d %d",&x,&y);
a[x].push_back(y);
a[y].push_back(x);
}
for(int i=1;i<=n;i++) scanf("%d",&w[i]);
for(int i=1;i<=n;i++)
{
l=a[i].size();
max1=-1001;
max2=-1001;
p=0,q=0;
if(l>1)
{
for(int j=0;j<l;j++)
{
v=a[i][j];
p=(p+w[v])%k;
q=(q+w[v]*w[v])%k;
if(w[v]>=max1)
{
max2=max1;
max1=w[v];
}
if(w[v]<max1&&w[v]>=max2) max2=w[v];
}
ans=(ans+p*p-q)%k;
maxn=max(maxn,max1*max2);
}
}
printf("%d %d",maxn,ans);
return 0;

}

注意
要开long long
不然只有70分
经典vector 拒绝bb
#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <vector>
#define N 10000000+100
using namespace std;
long long n,c[N],w[N],max1=-N,num,r,sum,m1,m2;
vector<int> flag[200001];
int main()
{
cin>>n;
for(int i=1;i<n;i++)
{
int x,y;
cin>>x>>y;
flag[x].push_back(y);
flag[y].push_back(x);
}
for(int i=1;i<=n;i++)
cin>>w[i];
for(int i=1;i<=n;i++)
{
sum=0;m1=0,m2=0;

for(int j=0;j<=flag[i].size()-1;j++)
{
sum+=w[flag[i][j]];
int x=w[flag[i][j]];
if(x>m1){m2=m1;m1=x;}
else
{
if(x>m2)m2=x;
}
}
for(int j=0;j<=flag[i].size()-1;j++)
num=(num+(sum-w[flag[i][j]])*w[flag[i][j]])%10007;
max1=max(max1,m1*m2);
}
cout<<max1<<" "<<num;
return 0;
}

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#define LL long long
using namespace std;
template <class _T> inline void read(_T &_x){
    int _t;bool _flag=0;
    while((_t=getchar())!='-'&&(_t>'9'||_t<'0'));
    if(_t=='-')_flag=1,_t=getchar();_x=_t-'0';
    while((_t=getchar())>='0'&&_t<='9')_x=_x*10+_t-'0';
    if(_flag)_x=-_x;
}
const int maxn=2e5+5;
const int MOD=10007;
int n,x,y,head[maxn],du[maxn],cnt;
LL w[maxn],ans1,ans2;
struct edge{
    int v,nxt;
}d[maxn<<1];
inline void add(int a,int b){
    d[++cnt].v=b;d[cnt].nxt=head[a];head[a]=cnt;
    d[++cnt].v=a;d[cnt].nxt=head[b];head[b]=cnt;
}


int main(){
    read(n);
    for(int i=1;i<n;++i){
        read(x),read(y);
        add(x,y);du[x]++;du[y]++;
    }
    for(int i=1;i<=n;++i){
        read(w[i]);
    }
    for(int i=1;i<=n;++i){
        if(du[i]<=1)continue;
        LL s1=0,s2=0,w1=0,w2=0;
        for(int k=head[i];k;k=d[k].nxt){
            int v=d[k].v;
            if(w1<w[v])w2=w1,w1=w[v];
            else if(w2<w[v])w2=w[v];
            s1+=w[v];s2+=w[v]*w[v];
            s1%=MOD;s2%=MOD;
        }
        ans1=max(ans1,w1*w2);
        ans2+=(s1*s1%MOD-s2+MOD)%MOD;ans2%=MOD;
    }
    printf("%lld %lld",ans1,ans2);
    
    return 0;
}

加一些小技巧。
#include <iostream>
using namespace std;
#include <queue>
#include <vector>
#include <algorithm>

#define INF 99999999
int val[200010];
int vis[200010]={0};
int dis[200010]={INF};
long long sum=0;
long long max1=0;
vector<int> G[200010];
long long s[200100]={0};
#include <cstdio>
int main(){

int n;
cin>>n;
for(int i=1;i<n;i++){
int from,to;
scanf("%d%d",&from,&to);
G[from].push_back(to);
G[to].push_back(from);
}
for(int i=1;i<=n;i++) cin>>val[i];
//bfs
long long maxa,maxb;

for(int i=1;i<=n;i++){
maxa=maxb=0;
for(int j=0;j<G[i].size();j++){
int v=G[i][j];
s[i]+=val[v];
if(val[v]>maxa) maxb=maxa,maxa=val[v];
else if(val[v]>maxb) maxb=val[v];
max1=max(max1,maxa*maxb);

}
for(int j=0;j<G[i].size();j++){
int v=G[i][j];
sum+=val[v]*(s[i]-val[v]);
sum%=10007;
}

}
cout<<max1<<" "<<sum%10007<<endl;
return 0;
}

#include <cstdio>
#include <vector>

using namespace std;

int n;
const int MOD = 10007;

vector<int> tree[200001];

int w[200001];

bool marked[200001];
vector<int> conn[200001];

long long f[200001];
int g[200001];

long long csum[200001];
long long ssum[200001];

int cmax[200001];
int csecond[200001];

void mk_tree(int node)
{
    marked[node] = true;
    for (int i = 0; i < conn[node].size(); i++) {
        if (!marked[conn[node][i]]) {
            tree[node].push_back(conn[node][i]);
            mk_tree(conn[node][i]);
        }
    }
}

void prepare(int node)
{
    for (int i = 0; i < tree[node].size(); i++) {
        int child = tree[node][i];
        csum[node] = (csum[node] + w[child]);
        ssum[node] = (ssum[node] + w[child]*w[child]);
        if (w[child] > cmax[node]) {
            csecond[node] = cmax[node];
            cmax[node] = w[child];
        } else if (w[child] > csecond[node]) {
            csecond[node] = w[child];
        }
        prepare(child);
    }
}

void calc(int node)
{
    for (int i = 0; i < tree[node].size(); i++) {
        int child = tree[node][i];
        calc(child);
        f[node] += f[child];
        g[node] = max(g[node], g[child]);
        f[node] += csum[child] * w[node];
        g[node] = max(g[node], cmax[child]*w[node]);
    }
    f[node] += (csum[node]*csum[node]-ssum[node])/2;
    g[node] = max(g[node], cmax[node]*csecond[node]);
}

int main()
{
    scanf("%d", &n);
    for (int i = 1; i < n; i++) {
        int u, v;
        scanf("%d%d", &u, &v);
        conn[u].push_back(v);
        conn[v].push_back(u);
    }
    for (int i = 1; i <= n; i++) {
        scanf("%d", w + i);
    }
    mk_tree(1);
    prepare(1);
    calc(1);
    printf("%d %d", g[1], (2*f[1])%MOD);
    return 0;
}

先在洛谷做的，但洛谷的数据似乎有问题，出现了权值为负的点
直接交到vijos上就过了
思路是枚举中间点，前缀和求乘积
整张图并不需要刻意储存（如果不是这个诡异的输入顺序的话）

#include<iostream>
using namespace std;
long long dp[200010],quan[200010],maxn[200010],minn[200010],qian[200010],hou[200010];
int main()
{
    int n,i,a,b;
    long long sum=0,ans=0;
    cin>>n;
    for(i=1;i<n;i++)
     cin>>qian[i]>>hou[i];
    for(i=1;i<=n;i++)
     cin>>quan[i];
    for(i=1;i<n;i++)
    {
        a=qian[i];
        b=hou[i];
        if(quan[a]>=maxn[b])
        {
            minn[b]=maxn[b];
            maxn[b]=quan[a];
        }
        else
        {
            if(quan[a]>minn[b])
             minn[b]=quan[a];
        }   
        if(quan[b]>=maxn[a])
        {
            minn[a]=maxn[a];
            maxn[a]=quan[b];
        }
        else
        {
            if(quan[b]>minn[a])
             minn[a]=quan[b];
        }
        sum+=2*dp[a]*quan[b];
        sum+=2*dp[b]*quan[a];
        dp[a]+=quan[b];
        dp[b]+=quan[a];
        sum%=10007;
    }
    for(i=1;i<=n;i++)
    {
        ans=max(ans,maxn[i]*minn[i]);
    }
    cout<<ans<<" "<<sum;
    return 0;
} 

中间量一定要用long long，经zjy提醒，输出用I64d，再次鸣谢zjy神犇！！！！
#include<bits/stdc++.h>
using namespace std;
const int MAXN=400005;
const int P=1e4+7;
long long w[MAXN],ans=0,maxn=0;
int n,a[MAXN],head[MAXN],Next[MAXN],tot=0;
void addedge(int u,int v)
{
a[++tot]=v;Next[tot]=head[u];head[u]=tot;
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n-1;i++){
int u,v;scanf("%d%d",&u,&v);
addedge(u,v);addedge(v,u);
}
for(int i=1;i<=n;i++){
scanf("%d",&w[i]);
}
for(int i=1;i<=n;i++){
long long sum=0;
int ji=0;
for(int j=head[i];j;j=Next[j]){
sum+=w[a[j]];++ji;
}
long long tmp=0;
for(int j=head[i];j;j=Next[j]){
tmp+=(sum-w[a[j]])*w[a[j]];
}
ans+=tmp;ans%=P;
if(ji>=2){
long long fir=0,sec=0;
for(int j=head[i];j;j=Next[j]){
if(w[a[j]]>fir)sec=fir,fir=w[a[j]];
else if(w[a[j]]>sec)sec=w[a[j]];
}
if(fir*sec>maxn)maxn=fir*sec;
}
}
printf("%I64d %I64d\n",maxn,ans);
}

#include <iostream>
#include <cstring>
#include <stdio.h>
using namespace std;

long long s[210000];
long long a[210000];
long long u[210000],v[210000];
long long max1[210000],max2[210000];
long long sum=0,maxi=0;

void bian(long long &x,long long &a,long long &b){
if(x>a){
b=a;
a=x;
}
else
if (x>b) b=x;
}

int main()
{
int n;
cin>>n;
for(int i=1;i<n;++i){
scanf("%lld %lld",&u[i],&v[i]);

}
for(int i=1;i<=n;++i){
cin>>a[i];

}
for(int i=1;i<n;++i){
long long u1=u[i];
long long v1=v[i];
s[u1]+=a[v1];
s[v1]+=a[u1];
bian(a[v1],max1[u1],max2[u1]);
bian(a[u1],max1[v1],max2[v1]);
}
for(int i=1;i<=n;++i){
if(max1[i]*max2[i]>maxi)
maxi=max1[i]*max2[i];
}
for(int i=1;i<n;++i){
long long u1=u[i];
long long v1=v[i];
sum=(sum+(s[u1]-a[v1])*a[v1]%10007)%10007;
sum=(sum+(s[v1]-a[u1])*a[u1]%10007)%10007;

}
cout<<maxi<<' '<<sum<<endl;
}

uses math;
var
b,e,d,f,g,fa:array [0..200005] of longint;
c:array [0..200005,1..2] of longint;
n,i,j,ans,x,y,t,p:longint;
procedure findmax(x:longint);
var i,p:longint;
begin
p:=d[x];
while (p<>0) do begin
findmax(p);
c[x,1]:=max(c[x,1],b[p]);
c[x,2]:=max(c[x,2],c[p,1]);
p:=g[p];
end;
end;
procedure findsum(x:longint);
var i,p:longint;
begin
p:=d[x];
while (p<>0) do begin
findsum(p);
c[x,1]:=(c[x,1]+b[p]) mod 10007;
c[x,2]:=(c[x,2]+c[p,1]) mod 10007;
p:=g[p];
end;
end;
begin
read(n);
for i:=1 to n-1 do
begin
read(x,y);
if (x=i+1) then begin t:=x; x:=y; y:=t; end;
if (d[x]=0) then begin d[x]:=y; f[x]:=y; end else begin g[f[x]]:=y; f[x]:=y; end;
fa[y]:=x;
end;
for i:=1 to n do read(b[i]);
findmax(1);
ans:=0;
for i:=1 to n do
begin
t:=c[i,2];
if (i<>1) then
if (b[i]<>c[fa[i],1]) then t:=max(t,c[fa[i],1])
else begin
x:=fa[i];
p:=d[x];
while (p<>0) do begin
if (p<>i) then t:=max(t,b[p]);
p:=g[p];
end;
end;
if (i<>1) and (fa[i]<>1) then t:=max(t,b[fa[fa[i]]]);
ans:=max(ans,t*b[i]);
end;
write(ans,' ');
fillchar(c,sizeof(c),0);
findsum(1);
ans:=0;
for i:=1 to n do
begin
t:=c[i,2];
if (i<>1) then t:=(t+c[fa[i],1]-b[i]+10007) mod 10007;
if (i<>1) and (fa[i]<>1) then t:=(t+b[fa[fa[i]]]) mod 10007;
ans:=(ans+t*b[i]) mod 10007;
end;
write(ans);
end.

#include<iostream>
#include<cstdio>
using namespace std;
int n;
long long x,y,ans1,ans2;
long long b[200001],s[200001],max1[200001],max2[200001];
struct ljh
{
long long u,v;
}a[200001];

void make(long long &x,long long &a,long long &b)
{
if(x>a)
{
b=a;
a=x;
}
else if(x>b)b=x;
}

int main()
{
scanf("%d",&n);
for(int i=1;i<n;i++)cin>>a[i].u>>a[i].v;
for(int i=1;i<=n;i++)cin>>b[i];
for(int i=1;i<n;i++)
{
x=a[i].u;y=a[i].v;
//遍历每条边连接的每个结点
s[x]+=b[y];//以x为起点的，加上新增的一个点的权值
s[y]+=b[x];//同理
make(b[y],max1[x],max2[x]);//更新以x为起点的最大权值与次大权值
make(b[x],max1[y],max2[y]);//同上
}
for(int i=1;i<=n;i++)
if(max1[i]*max2[i]>ans1)ans1=max1[i]*max2[i];
//计算出最大的联合权值，max1数组表示最大的与i相连的权值，max2数组
//表示次大的与i相连的数组，既然都与i相连，那么就肯定会两点之间的距离为2
for(int i=1;i<n;i++)
{
x=a[i].u;y=a[i].v;
ans2=(ans2+((s[x]-b[y])*b[y])%10007)%10007;
//所有与x点相连的点（除y外）的权值乘y点的权值
//因为都与x相连相连那么两点间距离肯定为2
ans2=(ans2+((s[y]-b[x])*b[x])%10007)%10007;
}
cout<<ans1<<" "<<ans2;
return 0;
}

为什么一个点周围的所有权值加起来会超过int,不应该是2000000000，离int上限还差1亿

#include <iostream>
#include <cstdio>
using namespace std;
int n,w[200005],s[200005],m[200005];
struct edge{int a;int b;}e[200005];
int main(){
    //freopen("input.txt","r",stdin);
    scanf("%d",&n);
    for(int i=0;i<n-1;i++)scanf("%d%d",&e[i].a,&e[i].b);
    for(int i=1;i<=n;i++)scanf("%d",&w[i]);
    for(int i=0;i<n-1;i++){
        int &x=e[i].a,&y=e[i].b;
        s[x]+=w[y],s[y]+=w[x];
        if(w[m[x]]<w[y])m[x]=y;
        if(w[m[y]]<w[x])m[y]=x;
    }
    for(int i=0;i<n-1;i++){
        int &x=e[i].a,&y=e[i].b;
        if(m[y]!=x&&w[x]*w[m[y]]>m[0])m[0]=w[x]*w[m[y]];
        if(m[x]!=y&&w[y]*w[m[x]]>m[0])m[0]=w[y]*w[m[x]];
        int u=(w[x]%10007)*((s[y]-w[x])%10007)%10007,v=(w[y]%10007)*((s[x]-w[y])%10007)%10007;
        if(u<0||v<0)
            printf(" ");
        s[0]=(s[0]+u+v)%10007;
    }
    printf("%d %d\n",m[0],s[0]);
    return 0;
}

编译成功

测试数据 #0: Accepted, time = 0 ms, mem = 12228 KiB, score = 10

测试数据 #1: Accepted, time = 0 ms, mem = 12232 KiB, score = 10

测试数据 #2: Accepted, time = 0 ms, mem = 12232 KiB, score = 10

测试数据 #3: Accepted, time = 0 ms, mem = 12232 KiB, score = 10

测试数据 #4: Accepted, time = 0 ms, mem = 12232 KiB, score = 10

测试数据 #5: Accepted, time = 0 ms, mem = 12232 KiB, score = 10

测试数据 #6: Accepted, time = 31 ms, mem = 12232 KiB, score = 10

测试数据 #7: Accepted, time = 109 ms, mem = 12224 KiB, score = 10

测试数据 #8: Accepted, time = 218 ms, mem = 12228 KiB, score = 10

测试数据 #9: Accepted, time = 218 ms, mem = 12228 KiB, score = 10

Accepted, time = 576 ms, mem = 12232 KiB, score = 100

代码
#include<stdio.h>
int count=0,max=0,point=0;
struct node
{
int v;int l;
}s[600050];
long long int tail=0;
int w[600050]={0};
long long int f[600050]={0};
void add(int u,int v )
{
point++;
s[point].v=v;
s[point].l=f[u];
f[u]=point;
}
int main()
{
int i,j,n,u,v;
scanf("%d",&n);
for(i=1;i<=n;i++)
f[i]=-1;
for(i=1;i<n;i++)
{
scanf("%d%d",&u,&v);
add(u,v);add(v,u);
}
for(i=1;i<=n;i++)
scanf("%d",&w[i]);
for(i=1;i<=n;i++)
{
int sum=0,sum1=0,max1=0,max2=0;
for(j=f[i];j!=-1;j=s[j].l)/*perfect*/
{
tail=w[s[j].v];
sum=(sum+tail)%10007;
sum1=(tail*tail+sum1)%10007;
if(tail>max1)
{
max2=max1;max1=tail;
}
else
if(tail>max2) max2=tail;
}
sum=sum*sum;
if(max2!=0) count=(count+sum-sum1)%10007;
if(max1*max2>max&&max2!=0) max=max1*max2;
}

printf("%d %d",max,count);
return 0;
}

var w,c:array[1..300000] of longint;
next,head,too:array[1..800000] of longint;
i,j:longint;
k,n,m,ans,max1,max2,u,v,s1,s2,p,s:int64;
begin
readln(n);
for i:=1 to n-1 do
begin
readln(u,v);
inc(c[u]);inc(c[v]);
inc(m);
too[m]:=v;
next[m]:=head[u];
head[u]:=m;
inc(m);
too[m]:=u;
next[m]:=head[v];
head[v]:=m;
end;
for i:=1 to n do read(w[i]);
for i:=1 to n do
if c[i]>1 then
begin
max1:=0;max2:=0;s1:=0;s2:=0;
p:=head[i];
while p<>0 do
begin
if w[too[p]]>max1 then begin max2:=max1;max1:=w[too[p]];end
else if w[too[p]]>max2 then max2:=w[too[p]];
s1:=s1+w[too[p]];s2:=s2+w[too[p]]*w[too[p]];
p:=next[p];
end;
s:=(s+s1*s1-s2)mod 10007;
if max1*max2>ans then ans:=max1*max2;
end;
s:=s mod 10007;
writeln(ans,' ',s);
end.

http://www.cnblogs.com/JSZX11556/p/4907703.html

//注意数据，我开int错3个点，开long long就过了
#include <cstdio>
#include <cstdlib>
#include <algorithm>

using namespace std;

struct Node
{
long long nextnode, val, sum;
long long first, second;
Node *next;
} pool[2000005], *N[200005];

int n, cnt;
int x[200005], y[200005];

int main(int argc, const char *argv[])
{
scanf("%d", &n);
for (int i = 1; i < n; ++i)
{
scanf("%d %d", &x[i], &y[i]);
Node *p = &pool[++cnt];
p->nextnode = y[i];
p->next = N[x[i]];
N[x[i]] = p;
p = &pool[++cnt];
p->nextnode = x[i];
p->next = N[y[i]];
N[y[i]] = p;
}
for (int i = 1; i <= n; ++i)
scanf("%d", &N[i]->val);
for (int i = 1; i < n; ++i)
{
N[x[i]]->sum += N[y[i]]->val;
N[y[i]]->sum += N[x[i]]->val;
if (N[y[i]]->val >= N[x[i]]->first)
{
N[x[i]]->second = N[x[i]]->first;
N[x[i]]->first = N[y[i]]->val;
}
else
{
if (N[y[i]]->val > N[x[i]]->second)
N[x[i]]->second = N[y[i]]->val;
}
if (N[x[i]]->val >= N[y[i]]->first)
{
N[y[i]]->second = N[y[i]]->first;
N[y[i]]->first = N[x[i]]->val;
}
else
{
if (N[x[i]]->val > N[y[i]]->second)
N[y[i]]->second = N[x[i]]->val;
}

}
long long ans1, ans2;
ans1 = ans2 = 0;
for (int i = 1; i <= n; ++i)
{
if (N[i]->first * N[i]->second > ans1)
ans1 = N[i]->first * N[i]->second;
for (Node *p = N[i]; p; p = p->next)
{
ans2 += N[p->nextnode]->val * (N[i]->sum - N[p->nextnode]->val);
ans2 %= 10007;
}
}
printf("%d %d\n", (int)(ans1), (int)(ans2));
return 0;
}

#include <cstdio>
#include <cstdlib>
#include <algorithm>

using namespace std;

struct Node
{
int nextNode;
Node *next;
} *p[200005], pool[200005];

int n, pool_count;
int length[200005];
int s[200005], t[200005], u[200005];
int s1[200005], t1[200005], u1[200005];
int first[200005], second[200005];

void dfs(int node)
{
for (Node *i = p[node]; i; i = i->next)
{
dfs(i->nextNode);
s[node] += length[i->nextNode];
s1[node] = max(s1[node], length[i->nextNode]);
t[node] += s[i->nextNode];
t1[node] = max(t1[node], s1[i->nextNode]);
s[node] %= 10007;
t[node] %= 10007;
}
for (Node *i = p[node]; i; i = i->next)
{
u[node] += length[i->nextNode] * (s[node] - length[i->nextNode]);
u[node] %= 10007;
}
for (Node *i = p[node]; i; i = i->next)
{
if (length[i->nextNode] >= first[node])
{
second[node] = first[node];
first[node] = length[i->nextNode];
}
if (length[i->nextNode] < first[node] && length[i->nextNode] > second[node])
{
second[node] = length[i->nextNode];
}
}
}
int main(int argc, const char *argv[])
{
scanf("%d", &n);
int x, y;
for (int i = 1; i < n; ++i)
{
scanf("%d %d", &x, &y);
if (x > y)
swap(x, y);
Node *d = &pool[pool_count++];
d->nextNode = y;
d->next = p[x];
p[x] = d;
}
for (int i = 1; i <= n; ++i)
{
scanf("%d", &x);
length[i] = x;
}
dfs(1);
int ans1, ans2;
ans1 = ans2 = 0;
int temp;
for (int i = 1; i <= n; ++i)
{
//printf("%d s:%d t:%d u:%d t1:%d\n", i, s[i], t[i], u[i], t1[i]);
ans2 += (t[i] * length[i] * 2 + u[i]);
temp = length[i] * t1[i];
if (temp > ans1)
ans1 = temp;
temp = first[i] * second[i];
if (temp > ans1)
ans1 = temp;
ans2 %= 10007;
}
printf("%d %d\n", ans1, ans2);
return 0;
}

其实题解很简单，答案1扫一遍图找**最大次大值**就好，答案2用一个**加法结合律**就好。贴个代码，就不要喷这**压行**习惯了。

#include<stdio.h>
#define mod 10007
#define max(a,b) (a>b?a:b)
long long ans1;int i,j,k,ans2,w[200001],n,s[200001],p1[200001],p2[200001],u[200000],v[200000];

int main(){
scanf("%d",&n);
for(i=0;i<n-1;++i)
scanf("%d%d",u+i,v+i);
for(i=1;i<=n;++i){
scanf("%d",w+i);w[i]%=mod;
}
for(i=0;i<n-1;++i){
s[u[i]]=(s[u[i]]+w[v[i]])%mod;s[v[i]]=(s[v[i]]+w[u[i]])%mod;
if(w[v[i]]>p1[u[i]]){p2[u[i]]=p1[u[i]];p1[u[i]]=w[v[i]];}
else if(w[v[i]]>p2[u[i]])p2[u[i]]=w[v[i]];
if(w[u[i]]>p1[v[i]]){p2[v[i]]=p1[v[i]];p1[v[i]]=w[u[i]];}
else if(w[u[i]]>p2[v[i]])p2[v[i]]=w[u[i]];
}
for(i=0;i<n-1;++i)
ans2=(ans2+(s[v[i]]-w[u[i]])*w[u[i]]%mod+(s[u[i]]-w[v[i]])*w[v[i]]%mod)%mod;
for(i=1;i<=n;++i) ans1=max(ans1,p1[i]*p2[i]);
printf("%lld %d\n",ans1,ans2);
return 0;
}