http://acm.hdu.edu.cn/showproblem.php?pid=4274
5 1 1 3 3 3 1 < 6 3 = 4 2 = 2 5 1 1 3 3 3 1 > 5 3 = 4 2 = 2
Lie True
/**
hdu 4274 树形dp
题目大意：一棵树，其部分节点给出一些不等关系，并且每个节点的值至少为1，祖先节点的总值必须大于该子树下值的总和。
解题思路：一开始想错了，例如代码后给出的第一例子是对的，我们只是保证子树的和不要超过祖先的最小限制就可以了。
对于没个节点维护一个最小值和一个最大值，初始化最小值为1，最大值为-1，没更新完一个节点比较最小值是否超过了
最大值就可以了。值得一提的是，输入可能就有矛盾的，因此在dfs一个节点的子树之前，要先进行判断。
*/
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <string.h>
using namespace std;
const int maxn=10005;
int head[maxn],ip;
bool judge;
int n,up[maxn],down[maxn];
void init()
{
memset(head,-1,sizeof(head));
ip=0;
}
struct note
{
int v,next;
}edge[maxn*2];
void addedge(int u,int v)
{
edge[ip].v=v,edge[ip].next=head[u],head[u]=ip++;
}
void dfs(int u,int pre)
{
if(up[u]!=-1&&down[u]>up[u])
{
judge=false;
return;
}
bool flag=0;
int ans=0;
for(int i=head[u];i!=-1;i=edge[i].next)
{
int v=edge[i].v;
if(pre==v)continue;
flag=1;
dfs(v,u);
ans+=down[v];
}
if(flag)
{
down[u]=max(down[u],ans+1);
if(up[u]!=-1&&down[u]>up[u])
judge=false;
}
}
int main()
{
while(~scanf("%d",&n))
{
init();
for(int i=2; i<=n; i++)
{
int v;
scanf("%d",&v);
addedge(i,v);
addedge(v,i);
}
for(int i=1;i<=n;i++)
{
up[i]=-1;
down[i]=1;
}
int m;
scanf("%d",&m);
while(m--)
{
int a,b;
char s[3];
scanf("%d%s%d",&a,s,&b);
if(s[0]=='<')
{
up[a]=b-1;
}
else if(s[0]=='>')
{
down[a]=b+1;
}
else
{
up[a]=down[a]=b;
}
}
judge=true;
dfs(1,-1);
if(judge)
puts("True");
else
puts("Lie");
}
return 0;
}
/**
5
1
1
3
3
3
4 < 3
3 = 5
5 < 3
5
1
1
3
3
3
1 > 5
3 = 4
2 = 2
**/
原文：http://blog.csdn.net/lvshubao1314/article/details/44564239