【luogu P1351 联合权值】 题解

题目链接：https://www.luogu.org/problemnew/show/P1351

做了些提高组的题，不得不说虽然NOIP考察的知识点虽然基本上都学过，但是做起题来还是需要动脑子的。
题目质量很高吧，觉得出的很有水平 （除了2017 d1t1

70分：
三层枚举强制到距离为2

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 2 * 1e6 + 10;
const int mod = 10007;
struct edge{
    long long from, to, next, len;
}e[maxn<<2];
long long head[maxn], cnt;
long long n, val[maxn], ans, maxx;
void add(long long u, long long v)
{
    e[++cnt].from = u;
    e[cnt].next = head[u];
    e[cnt].to = v;
    head[u] = cnt;
}
int main()
{
    memset(head, -1, sizeof(head));
    scanf("%lld",&n);
    for(long long i = 1; i < n; i++)
    {
        long long u, v;
        scanf("%lld%lld",&u,&v);
        add(u,v);
        add(v,u);
    }
    for(long long i = 1; i <= n; i++)
    scanf("%lld",&val[i]);
    
    /*for(long long i = 1; i <= cnt; i++)
    {
        cout<<i<<endl;
        cout<<e[i].from<<" "<<e[i].to<<" "<<e[i].next<<endl;
    }
    for(long long i = 1; i <= n; i++) cout<<head[i]<<" ";cout<<"qwq"<<endl;*/
    for(long long i = 1; i <= n; i++)
    {
        for(long long j = head[i]; j != -1; j = e[j].next)
        {
            for(long long k = head[e[j].to]; k != -1; k = e[k].next)
            {
                if(e[j].from != e[k].to)
                {
                    //cout<<e[j].from<<" "<<e[k].to<<endl;
                    if(maxx < val[e[j].from] * val[e[k].to])
                    maxx = val[e[j].from] * val[e[k].to];
                    ans += val[e[j].from] * val[e[k].to] % mod;
                }
            }
        }
    }
    cout<<maxx<<" "<<ans%mod;
}

100分：
每次枚举中间节点的所有儿子，再用完全平方公式倒退回去所有的2WiWj
这样做的复杂度为线性，如果强行组合所有方案是O(n^2)的

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 2 * 1e6 + 10;
const int mod = 10007;
struct edge{
    long long from, to, next, len;
}e[maxn<<2];
long long head[maxn], cnt;
long long n, val[maxn], ans, maxx, totsq, totsum, fir, sec;
void add(long long u, long long v)
{
    e[++cnt].from = u;
    e[cnt].next = head[u];
    e[cnt].to = v;
    head[u] = cnt;
}
int main()
{
    memset(head, -1, sizeof(head));
    scanf("%lld",&n);
    for(long long i = 1; i < n; i++)
    {
        long long u, v;
        scanf("%lld%lld",&u,&v);
        add(u,v);
        add(v,u);
    }
    for(long long i = 1; i <= n; i++)
    scanf("%lld",&val[i]);
    
    for(long long i = 1; i <= n; i++)
    {   
        fir = 0, sec = 0;
        long long  son1 = 0, son2 = 0;
        for(long long j = head[i]; j != -1; j = e[j].next)
        {
            if(val[e[j].to] > fir)
            {
                sec = fir;
                fir = val[e[j].to];
            }
            else if(val[e[j].to] > sec) 
            {
                sec = val[e[j].to];
            }
            son1 = (son1 + val[e[j].to]) % mod;
            son2 = (son2 + val[e[j].to] * val[e[j].to]) % mod;
        }
        if(sec == 0) continue;
        if(maxx < fir * sec)
        maxx = fir * sec;
        
        son1 = son1 * son1 % mod;
        ans = (ans + son1 - son2 + 10007)%10007;
    }
    printf("%lld %lld",maxx, ans);
    return 0;
}

【luogu P1351 联合权值】 题解

原文：https://www.cnblogs.com/MisakaAzusa/p/9642029.html