HDU 4274 Spy's Work（12年长春 树形DP）

转载请注明出处，谢谢http://blog.csdn.net/acm_cxlove/article/details/7854526 by---cxlove

题目：给出一棵树，给出一些子树的权值关系，问是否矛盾

http://acm.hdu.edu.cn/showproblem.php?pid=4274

初始对于所有结点以及子树的下限为1，上限可能不确定

然后通过给出的不等式去更新上下界，之后进行树形DP，通过孩子的下界更新父节点的下界

再判断是否矛盾

注意当前节点当个的权值下限为1，该节点的下限为孩子下界的和+1

#include<iostream>#include<cstdio>#include<map>#include<cstring>#include<cmath>#include<vector>#include<algorithm>#include<set>#define inf 110000000#define M 10005#define N 10005#define Min(a,b) ((a)<(b)?(a):(b))#define Max(a,b) ((a)>(b)?(a):(b))#define pb(a) push_back(a)#define mem(a,b) memset(a,b,sizeof(a))#define LL long long#define MOD 1000000007using namespace std;struct Node{int v,next;}edge[N*2];int n,start[N],tot;int up[N],low[N];void addedge(int u,int v){edge[tot].v=v;edge[tot].next=start[u];start[u]=tot++;}void _addedge(int u,int v){addedge(u,v);addedge(v,u);}bool ans;void dfs(int u,int pre){if(ans) return;if(up[u]!=-1&&low[u]>up[u]){ans=true;return;}int tmp=0;int leaf=1;for(int i=start[u];i!=-1;i=edge[i].next){int v=edge[i].v;if(v==pre) continue;dfs(v,u);leaf=0;tmp+=low[v];}if(leaf) return;low[u]=max(tmp+1,low[u]);if(up[u]!=-1&&low[u]>up[u]) ans=true;}int main(){while(scanf("%d",&n)!=EOF){tot=0;mem(start,-1);for(int i=2;i<=n;i++){int u;scanf("%d",&u);_addedge(u,i);}int m;for(int i=1;i<=n;i++){low[i]=1;up[i]=-1;}scanf("%d",&m);for(int i=0;i<m;i++){int u,w;char str[5];scanf("%d%s%d",&u,str,&w);if(str[0]=='<') up[u]=w-1;else if(str[0]=='>') low[u]=w+1;else low[u]=up[u]=w;}ans=false;dfs(1,0);puts(ans?"Lie":"True");}return 0;}