Description

无向连通图 \(G\) 有 \(n\) 个点， \(n-1\) 条边。点从 \(1\) 到 \(n\) 依次编号,编号为 \(i\) 的点的权值为 \(W_i\) ，每条边的长度均为 \(1\) 。图上两点 \((u, v)\) 的距离定义为 \(u\) 点到 \(v\) 点的最短距离。对于图 \(G\) 上的点对 \((u, v)\) ，若它们的距离为 \(2\) ，则它们之间会产生 \(W_v \times W_u\) 的联合权值。

Input

第一行包含 \(1\) 个整数 \(n\) 。

接下来 \(n-1\) 行,每行包含 \(2\) 个用空格隔开的正整数 \(u,v\) ，表示编号为 \(u\) 和编号为 \(v\) 的点之间有边相连。

最后 \(1\) 行,包含 \(n\) 个正整数，每两个正整数之间用一个空格隔开，其中第 \(i\) 个整数表示图 \(G\) 上编号为 \(i\) 的点的权值为 \(W_i\) 。

Output

输出共 \(1\) 行,包含 \(2\) 个整数，之间用一个空格隔开,依次为图 \(G\) 上联合权值的最大值和所有联合权值之和。由于所有联合权值之和可能很大，输出它时要对 \(10007\) 取余。

Sample Input

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

Sample Output

20 74

Hint

对于100%的数据， \(1 \leq n \leq 200000, 0 \leq W_i \leq 10000\) 。

Solution

比较显然的树形递推。

我们考虑对于一棵树，如果能知道根节点的所有以他的儿子为根的子树的答案，可以非常方便的得到以根节点为根的树的答案。这样状态就得以确定了。我们使用\(f(i)\)来代表以i为根的子树的答案。

对于转移，我们考虑根节点的答案首先是儿子的累加和，其次，根节点对孙子能够构成联合权值，这些都可以在枚举儿子的时候方便的计算出来。最后考虑任意儿子之间会产生联合权值。朴素做法当然是把儿子都存下来然后互相乘起来，这样的复杂度是\(O(n^2)\)，会被菊花图卡吐血。

因为前面的儿子\(\times\)后面的儿子显然等于反过来乘，所以我们只需要前面的儿子\(\times\)后面的，最后把答案乘二即可。考虑对于根节点的第\(i\)个儿子，它对答案的贡献是【它的权值乘上它前面\(i-1\)儿子的权值的积】的和，根据乘法结合律，提取该节点的权值，它对答案的贡献就是它的权值乘上【前面儿子的的权值的和】的积这样我们可以直接维护他前面所有儿子的和，然后乘上该节点的权值，加入答案即可。

Code

#include
    
     #include
     
      #include
      
       #define rg register#define ci const int#define cl const long long inttypedef long long int ll;namespace IO {    char buf[50];}template
       
        inline void qr(T &x) {    char ch=getchar(),lst=' ';    while(ch>'9'||ch<'0') lst=ch,ch=getchar();    while(ch>='0'&&ch<='9') x=(x<<1)+(x<<3)+(ch^48),ch=getchar();    if (lst=='-') x=-x;}template
        
         inline void write(T x,const char aft,const bool pt) {    if(x<0) {putchar('-');x=-x;}    int top=0;    do {        IO::buf[++top]=x%10+'0';        x/=10;    } while(x);    while(top) putchar(IO::buf[top--]);    if(pt) putchar(aft);}template 
         
          inline T mmax(const T &a,const T &b) {if(a>b) return a;return b;}template 
          
           inline T mmin(const T &a,const T &b) {if(a
           
            inline T mabs(const T &a) {if(a<0) return -a;return a;}template 
            
             inline void mswap(T &a,T &b) {T temp=a;a=b;b=temp;}const int maxn = 200010;const int maxm = 400010;const int MOD = 10007;struct Edge { int to,nxt;};Edge edge[maxm];int hd[maxn],ecnt;inline void cont(ci from,ci to) { Edge &e=edge[++ecnt]; e.to=to;e.nxt=hd[from];hd[from]=ecnt;}int a,b;int n,ans;int MU[maxn];int frog[maxn];void dfs(ci,ci);int main() { srand(time(NULL)); qr(n); for(rg int i=1;i
             
              =_ans1) _ans2=_ans1,_ans1=MU[to];else if(MU[to]>_ans2) _ans2=MU[to]; ans=mmax(ans,_ans1*_ans2); dfs(to,k); frog[k]=(frog[k]+frog[to])%MOD; for(rg int j=hd[to];j;j=edge[j].nxt) { int &tt=edge[j].to; if(tt==k) continue; int _a=MU[tt]*MU[k]; frog[k]=(frog[k]+_a)%MOD; ans=mmax(ans,_a); } }}
             
            
           
          
         
        
       
      
     
    

Summary

当发现一个小部分因为复杂度超标而不可做的时候，不妨通过一些数学分析将复杂度降低从而获得正确的复杂度