JSOI2010蔬菜庆典：树结构中的无限大权值问题

#include 
#include 
#include 
#include 
#include 
using namespace std;
typedef long long ll;
inline int read() {
    int x = 0, f = 1; char ch = getchar();
    while (ch <'0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = (x <<1) + (x <<3) + (ch ^ 48); ch = getchar(); }
    return x * f;
}
const int N = 2e5 + 7;
int n, a[N]; // 权值
ll ans, res, b[N], ss; // 答案，中间答案，差分数组，叶子节点权值和
int fir[N], from[N <<1], to[N <<1], cntt;
inline void add(int a, int b) { from[++cntt] = fir[a]; fir[a] = cntt; to[cntt] = b; }
int rt, son[N], fa[N]; // 根，任意一个儿子，父亲
bool GG, flag; // 是否+inf, 子树是否权值一样
void dfs(int x) {
    int u = son[x]; res += a[x];
    if (!son[x]) ss += a[x];
    for (int i = fir[x]; i; i = from[i]) {
        int &v = to[i];
        if (a[v] != a[u]) { GG = 1; return; }
        if (a[fa[x]] + a[v] != 2 * a[x]) flag = 1;
        fa[v] = x; dfs(v);
    }
}
int dfs2(int x) // 判断除去叶子是否是一条链
{
    int cnt = 0, pd = 0;
    for (int i = fir[x]; i; i = from[i]) cnt++, pd |= dfs2(to[i]);
    if (pd && cnt >= 2) GG = 1;
    return cnt > 0;
}
inline bool cmp(ll &a, ll &b) { return a > b; }
int val[N], tot;
void dfs3(int x) // 走链
{
    val[++tot] = a[x];
    if (son[x]) dfs3(son[x]);
}
void solve(int x) // 处理一个子树
{
    flag = res = ss = 0; fa[x] = rt; dfs(x);
    if (GG) return;
    if (flag) dfs2(x); // 如果权值会变，看看是否为链
    if (GG) return;
    if (!flag) { ans += res; return; } // 权值不变直接把整个子树权值计入答案
    tot = 0; dfs3(x); val[0] = a[rt];
    for (int i = 1; i <= tot; i++) b[i] = val[i] - val[i-1]; // 差分
    sort(b + 1, b + tot + 1, cmp); ll now = a[rt];
    for (int i = 1; i     ans += ss; // 记得加上叶子
}
inline void clr() {
    cntt = GG = flag = rt = ans = res = tot = ss = 0;
    for (int i = 1; i <= n; i++) a[i] = b[i] = son[i] = fa[i] = fir[i] = val[i] = 0;
}
int main() {
    while (233) {
        n = read(); if (!n) break;
        int fa;
        for (int i = 1; i <= n; i++) {
            fa = read(), a[i] = read();
            if (fa == -1) rt = i;
            else add(fa, i), son[fa] = i;
        }
        for (int i = fir[rt]; i; i = from[i]) {
            solve(to[i]); if (GG) break;
        }
        if (GG) printf("+inf\n");
        else printf("%lld\n", ans + a[rt]);
        clr();
    }
    return 0;
}