喵哈哈村与哗啦啦村的大战（四）

发布时间: 2017年3月28日 20:03   最后更新: 2017年3月28日 20:06   时间限制: 1000ms   内存限制: 128M

描述

喵哈哈村因为和哗啦啦村争夺稀有的水晶资源，展开了激烈的战斗！

喵哈哈村的部落可以视为由n个节点组成，其中有n-1条边连接这n个节点，使得任意两个节点都会有一条路径相连接。每个节点上都有一个点权a[i]。

如果说存在一条路径上的权值满足非严格的单调递增或者非严格的单调递减的话，就说这条路径是一条好路径。

现在问题来了，给你一棵树，问你这棵树上有多少条路径是好路径。

输入

本题包含若干组测试数据。
第一行一个n，表示有n个节点。
第二行n个整数a[i]，表示节点的权值。
接下来n-1行每行两个整数x,y。表示x,y节点之间有一条边相互连接。

满足：1<=n<=100000 1<=a[i]<=1e9 1<=x,y<=n

输出

输出好路径的个数。

样例输入1 
复制 

4
1 7 1 9
1 3
1 4 
2 1

样例输出1 

5

样例输入2 
复制 

6
1 1 2 2 3 3
1 2
2 3
3 4
4 5
5 6

样例输出2 

15

查看隐藏信息
选择语言

 C (GCC 4.8) 
 C++ (G++ 4.3) 
 Java (Oracle JDK 1.7)

dp[i][0]:表示到i点的权值非递减路径的条数

dp[i][1]:表示到i点的权值非递增路径的条数

dp[i][2]:表示路径上权值相等的路径的条数 


#include<vector>
#include <stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
typedef long long ll;
#define maxn 100005
vector<ll>q[maxn];
ll n,a[maxn],dp[maxn][3],ans;
void dfs(ll u,ll p)
{
	ll i,up=0,down=0,low=0;
	for(i=0;i<q[u].size();i++)
	{
		ll v=q[u][i];
		if(v==p)
			continue;
		dfs(v,u);                             
		if(a[u]>=a[v])
			dp[u][0]+=dp[v][0]+1,up+=dp[v][0]+1;    
		if(a[u]<=a[v])
			dp[u][1]+=dp[v][1]+1,low+=dp[v][1]+1;
		if(a[u]==a[v])      
			dp[u][2]+=dp[v][2]+1,down+=dp[v][2]+1;
	}                        
	ans+=dp[u][0]+dp[u][1]-dp[u][2];
	for(i=0;i<q[u].size();i++)
	{
		ll v=q[u][i];
		if(v==p)
			continue;
		if(a[u]>a[v])
		{
			up-=dp[v][0]+1;
			ans+=(dp[v][0]+1)*low;
		}                   
		else if(a[u]<a[v])
		{
			low-=dp[v][1]+1;
			ans+=(dp[v][1]+1)*up;
		}
		else
		{
			up-=dp[v][0]+1;
			low-=dp[v][1]+1;
			down-=dp[v][2]+1;
			ans+=(dp[v][0]+1)*low;
			ans+=(dp[v][1]+1)*up;
			ans-=(dp[v][2]+1)*down;
		}
	}
}
int  main()
{
	ll i,x,y;
	while(scanf("%lld",&n)!=EOF)
	{
		 ans=0;
		 memset(dp,0,sizeof(dp));
		 for(i=1;i<=n;i++)
			 scanf("%lld",&a[i]);
		 for(i=1;i<=n-1;i++)
		 {
			 scanf("%lld%lld",&x,&y);
			 q[x].push_back(y);
			 q[y].push_back(x);                    
		 }
		 dfs(1,0);
		 printf("%lld/n",ans);
		 for(i=1;i<=n;i++)
			 q[i].clear();
	}
}