【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;

}