[UOJ 16]联合权值

danihao123 posted @ 2016年9月10日 20:59 in 题解 with tags 枚举 NOIP uoj , 166 阅读
转载请注明出处:http://danihao123.is-programmer.com/

这个题的关键啊……就在于那个中间点。

我们可以枚举中间点,然后进行统计。

至于最大联合权值,直接找中间点相邻点中最大权值和次大权值的积的最大值。至于联合权值之和,可以推出这样一个式子([tex]x[/tex]与中间点相邻,其中[tex]s[/tex]是所有和中间点相邻的点的权值和):

[tex]\Sigma x\mul (s-x)[/tex]

这就好弄多了。

代码:

#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn=2*1e5+5;
const int maxm=maxn*2,MOD=10007;
#define REP(i,n) for(i=1;i<=(n);i++)
#define GRAPH_REP(i,u) for(i=first[u];i;i=next[i])
int first[maxn];
int next[maxm],to[maxm];
int graph_tot=0;
inline void AddEdge(int u,int v){
    graph_tot++;
    next[graph_tot]=first[u];
    first[u]=graph_tot;
    to[graph_tot]=v;
}

// int pow_mod(int a,int b){
//     if(!b){
//         return 1;
//     }
//     int x=pow_mod(a,b>>1);
//     long long ans=(((long long)x)*((long long)x))%MOD;
//     if(1&b)
//         ans=ans*(a%MOD)%MOD;
//     return (int)ans;
// }
int d[maxn];
int main(){
    int n,u,v,temp,temp2;
    register int i,j,ans1=0,ans2=0,sum,maxv,smax;
    scanf("%d",&n);
    REP(i,n-1){
        scanf("%d%d",&u,&v);
        AddEdge(u,v);
        AddEdge(v,u);
    }
    REP(i,n){
        scanf("%d",&d[i]);
    }
    REP(i,n){
        sum=maxv=smax=0;
        GRAPH_REP(j,i){
            temp=to[j];
            sum=(d[temp]%MOD+sum)%MOD;
            if(d[temp]>maxv){
                smax=maxv;
                maxv=d[temp];
            }else{
                if(d[temp]>smax)
                    smax=d[temp];
            }
        }
        ans1=max(ans1,maxv*smax);
        temp2=0;
        GRAPH_REP(j,i){
            temp=to[j];
            temp2=(temp2+(d[temp]%MOD)*((sum-(d[temp]%MOD)+MOD)%MOD)%MOD)%MOD;
        }
        ans2=(ans2+temp2)%MOD;
    }
    printf("%d %d\n",ans1,ans2);
    return 0;
}

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter