记录编号	345105	评测结果	AAAAAAAAAA
题目名称	[NOIP 2014]联合权值	最终得分	100
用户昵称	Phosphorus15	是否通过	通过
代码语言	C++	运行时间	0.502 s
提交时间	2016-11-10 20:01:14	内存使用	3.02 MiB

#include <iostream>
#include <cstdio>
#include <vector>

//using std::cin;
//using std::cout;
//using std::endl;
using std::vector;

const char endl = '\n';

struct output{
  output & operator <<(long long i){
    printf("%lld",i);
    return *this;
  }
  output & operator <<(int i){
    printf("%d",i);
    return *this;
  }
  output & operator <<(char c){
    putchar(c);
    return *this;
  }
  output & operator <<(const char * cs){
    printf("%s",cs);
    return *this;
  }
}cout;

struct input{
  input & operator >>(int &i){
    char c = getchar();
    i = 0;
    while(!(c>='0'&&c<='9'))
      c = getchar();
    while(c>='0'&&c<='9'){
      i = i * 10 + (c-'0');
      c = getchar();
    }
    return * this;
  }
  input & operator >>(long long &i){
    char c = getchar();
    i = 0;
    while(!(c>='0'&&c<='9'))
      c = getchar();
    while(c>='0'&&c<='9'){
      i = i * 10 + (c-'0');
      c = getchar();
    }
    return * this;
  }
}cin;

struct Node{
  long long w,t;
  vector<int> adjs;
  int operator [](int x){
    return adjs[x];
  }
};

int n,maxn = 0;
long long sum = 0;
Node nodes[200001];

int run(){
  freopen("linkb.in","r",stdin);
  freopen("linkb.out","w+",stdout);
  int u,v,s;
  cin>>n;
  for(int x=0;x not_eq (n-1);x++){
    cin>>u>>v;
    if(u==v)
      continue;
    u--,v--;
    nodes[u].adjs.push_back(v);
    nodes[v].adjs.push_back(u);
  }
  for(int x=0;x not_eq n;x++){
    cin>>nodes[x].w;
    for(vector<int>::iterator it = nodes[x].adjs.begin();it!=nodes[x].adjs.end();it++){
      nodes[*it].t += nodes[x].w;
    }
  }
  for(int x=0;x!=n;x++){
    int maxf = 0,maxs = 0;
    for(int y=0;nodes[x].adjs.size() > y;y++){
      //cout<<"node "<<x<<' '<<y<<endl;
      u = nodes[nodes[x][y]].w;
      if(u>=maxf){maxs = maxf;maxf = u;}
      sum += u * (nodes[x].t - u);
      sum %= 10007;
    }
    int r = maxf * maxs;
    maxn = (r>maxn)?r:maxn;
  }
  cout<<maxn<<' '<<(int)(sum)<<endl;
  return 0;
}

int rvalue(run());

int main(int argc,char ** argv){
  return 0;
}