题解【luoguP1351 NOIp提高组2014 联合权值】

题目链接

题意：给定一个无根树，每个点有一个权值。若两个点 \(i,j\) 之间距离为\(2\)，则有联合权值 \(w_i \times w_j\)。求所有的联合权值的和与最大值

分析：

暴力求，每个节点遍历一遍周围的点，对每个点再遍历一次
可以拿到70分
考虑正解。对于一个点\(u\)，周围一圈可以到达的点中，从中任选两个不同的点\(i,j\)，则这两个点构成联合权值。
所以我们对一个点维护三个值：周围一圈点\(w_i\)之和\(sumw_u\)，\(w_i\)的最大值\(first_u\)，\(w_i\)的次大值\(second_u\)
则在\(u\)周围一圈选取一个点\(i\)与圈上的其他点的所有联合权值之和为\(w_i \times (sumw_u-w_i)\)；对于\(u\)周围一圈联合权值最大值为\(first_u \times second_u\)
用dfs求一遍就行了

实现：

第一遍dfs求每个点的三个值
第二遍求答案
复杂度\(O(n)\)

注意事项：

取膜！
long long!

代码：

#include <iostream>

#include <cstdlib>

#include <cstdio>

#include <cstring>

using namespace std;

#define int long long

const int MAXN = 200200;

const int MOD = 10007;

int n, w[MAXN], cnt, Max = 0, ans, sumw[MAXN], vis1[MAXN], vis2[MAXN], first[MAXN], second[MAXN];

struct edge

{

	int v; edge *next;

}pool[MAXN << 1], *head[MAXN];

inline void addedge(int u, int v)

{

	edge *p = &pool[++cnt], *q = &pool[++cnt];

	p->v = v, p->next = head[u]; head[u] = p;

	q->v = u, q->next = head[v]; head[v] = q;

}

void dfs1(int u)

{

	vis1[u] = 1;

	for(edge *p = head[u]; p; p = p->next)

	{

		sumw[u] += w[p->v];

		if(first[u] < w[p->v]) second[u] = first[u], first[u] = w[p->v];

		else second[u] = max(second[u], w[p->v]);

		if(!vis1[p->v]) dfs1(p->v);

	}

}

void dfs2(int u)

{

	vis2[u] = 1;

	Max = max(Max, first[u] * second[u]);

	for(edge *p = head[u]; p; p = p->next)

	{

		int lh = sumw[u] * w[p->v] - w[p->v] * w[p->v];

		ans = (ans + lh) % MOD;

		if(!vis2[p->v]) dfs2(p->v);

	}

}

#undef int

int main()

{

	memset(second, -1, sizeof(second));

	scanf("%d", &n);

	for(int i = 1; i < n; i++)

	{

		int u, v;

		scanf("%d%d", &u, &v);

		addedge(u, v);

	}

	for(int i = 1; i <= n; i++) scanf("%lld", &w[i]);

	dfs1(1);

	dfs2(1);

	printf("%lld %lld", Max, ans);

    return 0;

}

巴特西

题解【luoguP1351 NOIp提高组2014 联合权值】

最新文章

热门文章