学步园

题意：给定一棵节点为n（n<=10000）的树，每一个节点代表一个员工，1为boss节点，现在有若干个约束，
          即u<（=>）w代表以u节点为根节点的员工权值和<（=>）w，问给定的m（m<=10000）个约数之间是否有冲突。
题解：维护每棵子树的最大最小可能值（或者确定值，如果是 "=" 的话）。

Sure原创，转载请注明出处。

#include <iostream>
#include <cstdio>
#include <memory.h>
#define MIN(a , b) ((a) < (b) ? (a) : (b))
#define MAX(a , b) ((a) > (b) ? (a) : (b))
using namespace std;
const __int64 inf = (~(0ULL) >> 1);
const int maxn = 10002;
struct node
{
    int v;
    int next;
}edge[maxn << 1];
struct ans
{
    __int64 val,l,r;
}dp[maxn];
int head[maxn],sum[maxn];
int m,n,idx;
bool flag;

void init()
{
    memset(head,-1,sizeof(head));
    idx = 0;
    flag = true;
    for(int i=1;i<=n;i++)
    {
        dp[i].val = dp[i].l = -1;
        dp[i].r = inf;
    }
    return;
}

void addedge(int u,int v)
{
    edge[idx].v = v;
    edge[idx].next = head[u];
    head[u] = idx++;

    edge[idx].v = u;
    edge[idx].next = head[v];
    head[v] = idx++;
    return;
}

void read()
{
    char str[3];
    int u,w;
    for(int i=2;i<=n;i++)
    {
        scanf("%d",&u);
        addedge(i,u);
    }
    scanf("%d",&m);
    while(m--)
    {
        scanf("%d %s %d",&u,str,&w);
        if(str[0] == '=')
        {
            dp[u].val = w;
        }
        else if(str[0] == '<')
        {
            dp[u].r = w-1;
        }
        else dp[u].l = w+1;
    }
    return;
}

void dfs(int st,int pre)
{
    sum[st] = 1;
    for(int i=head[st];i != -1;i=edge[i].next)
    {
        if(edge[i].v == pre) continue;
        dfs(edge[i].v , st);
        sum[st] += sum[edge[i].v];
    }
    if(dp[st].l == -1 || dp[st].l < sum[st]) dp[st].l = sum[st];
    return;
}

void DFS(int st,int pre)
{
    if(flag == false) return;
    bool leaf = true;
    __int64 ll = 1,rr = 1;
    for(int i=head[st];i != -1;i=edge[i].next)
    {
        if(edge[i].v == pre) continue;
        leaf = false;
        DFS(edge[i].v , st);
        if(dp[edge[i].v].val != -1)
        {
            ll += dp[edge[i].v].val;
            if(rr < inf) rr += dp[edge[i].v].val;
        }
        else
        {
            ll += dp[edge[i].v].l;
            if(dp[edge[i].v].r == inf)
            {
                rr = inf;
            }
            else rr += dp[edge[i].v].r;
        }
    }
    if(leaf == false)
    {
        if(ll > dp[st].r)
        {
            flag = false;
            return;
        }
        if(ll > dp[st].l) dp[st].l = ll;
    }
    if(dp[st].val != -1)
    {
        if(dp[st].val < dp[st].l || dp[st].val > dp[st].r)
        {
            flag = false;
            return;
        }
    }
    else if(dp[st].l > dp[st].r)
    {
        flag = false;
        return;
    }
    else if(dp[st].l == dp[st].r)
    {
        dp[st].val = dp[st].l;
    }
    return;
}

int main()
{
    while(~scanf("%d",&n))
    {
        init();
        read();
        dfs(1,0);
        DFS(1,0);
        puts(flag ? "True" : "Lie");
    }
    return 0;
}