随笔档案

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define inf 1000000100
const int maxn = 10100 , maxm = 300300;
int n , m;
struct Edge {
    int v,next;   
}edge[maxm];
int  E,head[maxn];
int least[maxn] , most[maxn];
void init() {
    for(int i=1;i<=n;i++) {
        head[i] = -1;
        least[i] = 1;
        most[i] = inf;   
    }   
}
void addedge(int u,int v) {
    edge[E].v=v;edge[E].next=head[u];head[u]=E++;   
}
void dfs(int u) {
    int leastt = 1;
    for(int i=head[u];i!=-1;i=edge[i].next) {
        int v = edge[i].v;
        dfs(v);
        leastt += least[v];
    }    
    if(least[u] < leastt) least[u] = leastt;
}
int main() {
    while(~scanf("%d",&n)) {
        init();
        for(int i=2;i<=n;i++) {
            int u;
            scanf("%d",&u);
            addedge(u,i);   
        }   
        scanf("%d",&m);
        int u , val;
        char ch[5];
        for(int i=0;i<m;i++) {
            scanf("%d%s%d",&u,ch,&val);
            if(ch[0] == '=') {
                if(least[u] <= val) least[u] = val;
                if(most[u] >= val) most[u] = val;   
            }
            if(ch[0] == '<') {
                if(most[u] >= val - 1) most[u] = val - 1;   
            }
            if(ch[0] == '>') {
                if(least[u] <= val + 1) least[u] = val + 1;   
            }
        }
        dfs(1);
        int ok = 1;
        for(int i=1;i<=n;i++) {
            if(least[i] > most[i]) {
                ok =  0;
                break;   
            }   
        }
        if(ok) puts("True");
        else puts("Lie");
    }
    return 0;   
}