HN Training 2015 Round9 Water（乱搞）

发表于 |
字数统计: 417字 | 阅读时长 ≈ 2min

这个题比较简单，考虑先找到树中最高的节点$x$，那么水位有两种情况，要么各个子树的水位都不超过$H[x]$，要么大于$H[x]$就会让所有点的水位的一样，因此可以直接递归处理出子树的方案数$F[sub]$，

那么$F[x]=\prod F[sub]+m-H[x]$，直接暴力分治下去就行了。

这题可以用排序并查集或者一种快速查找区间最大值的数据结构优化成$O(n\log n)$，但是数据范围小，没有必要。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<cstring>
#define N 2005
using namespace std;
const int mod=1e9+7;
void add(int &x,int y){x+=y;x-=x>=mod?mod:0;}
int mul(int x,int y){return 1ll*x*y%mod;}
int n,m,H[N],Max,rt;
int TOT,LA[N],NE[N],EN[N];
bool mark[N];
void ADD(int x,int y)
{
	TOT++;
	EN[TOT]=y;
	NE[TOT]=LA[x];
	LA[x]=TOT;
}
void Grt(int x,int f)
{
	if(H[x]>Max)Max=H[x],rt=x;
	for(int i=LA[x];i;i=NE[i])
	{
		int y=EN[i];
		if(y!=f&&!mark[y])Grt(y,x);
	}
}
int Cal(int x,int y)
{
	int i,j,k,t,ans=1;mark[x]=1;
	for(i=LA[x];i;i=NE[i])
	{
		t=EN[i];if(mark[t])continue;
		Max=-1;Grt(t,x);
		ans=mul(ans,Cal(rt,H[x]));
	}
	add(ans,y-H[x]);
	return ans;
}
int main()
{
	int i,j,k,x,y;
	scanf("%d%d",&n,&m);
	for(i=1;i<n;i++)
	{
		scanf("%d%d",&x,&y);
		ADD(x,y);ADD(y,x);
	}
	for(i=1;i<=n;i++)scanf("%d",&H[i]);
	Max=-1;Grt(1,0);printf("%d",Cal(rt,m));
}