首页 > 其他 > 详细

P1351 联合权值

时间:2019-01-22 00:26:49      阅读:156      评论:0      收藏:0      [点我收藏+]

  为了写一写LCA,我就按照标签找……结果这道题我写完竟然没用LCA……真是神奇。。。

  很多人(包括我),首先就想到了要枚举每一个点,再枚举任意这个点的两个儿子,可是显然O(n2)会T……

  其实我们只要线性扫一遍就可以了,利用小学学到的乘法分配率,边走边加val,这样下一个点和val的乘积就是它和这之前所有的点的乘积之和,最后就是sum。

  当然,点对反过来就是一组新的点对,所以,随后的sum要乘2。

  而对于最大值,只要每一次更新我扫过的这些点权里最大的数是多少(在一次外层循环中),和新的点权相乘,看看能不能更新最大解即可。

  对了,记得看看是给谁取模。

  代码如下:

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
#define maxn 4000000
#define mod 10007
#define int long long 
int head[maxn],to[maxn],nxt[maxn],w[maxn];
int n,cnt;
void add(int a,int b)
{
    to[++cnt]=b;
    nxt[cnt]=head[a];
    head[a]=cnt;
}
main()
{
    scanf("%lld",&n);
    for(int i=1;i<=n-1;i++)
    {
        int a,b;
        scanf("%lld%lld",&a,&b);
        add(a,b);
        add(b,a);
    } 
    for(int i=1;i<=n;i++)
    scanf("%lld",&w[i]);
    int sum=0,Max=0;
    int fir,val,maxpo;
    for(int i=1;i<=n;i++)
    {
        fir=head[i];
        val=w[to[fir]]%mod;
        maxpo=w[to[fir]];
        fir=nxt[fir];
        for(; fir; fir=nxt[fir])
        {
            sum=(sum+val*w[to[fir]])%mod;
            val=(val+w[to[fir]])%mod;
            Max=max(Max,maxpo*w[to[fir]]);
            maxpo=max(maxpo,w[to[fir]]);
        }
    }
    printf("%lld %lld",Max,(2*sum)%mod);
    return 0; 
}

 

P1351 联合权值

原文:https://www.cnblogs.com/popo-black-cat/p/10301580.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!