hdu_5420 Victor and Proposition

题目:

  At the very beginning, Victor has a proposition, then this proposition procudes many propositions. Then every proposition procudes more propositions...... Finally there are propositions. These propositions can be regarded as a tree whose root is .
  We assume that the first proposition, whose number is , belongs to the -th generation, and those propositions produced by the -th generation belong to the -th generation. We also assume that all of the propositions in the -th generation are in level . Specially, Victor has discovered that the proposition whose number is can infer the proposition whose number is and all of the propositions in 's subtree, whose levels are not greater than 's level + .
  Notice : a is b's father does not show that either a can infer b or b can infer a.
  Now please determine the number of such ordered pairs , that , the proposition can infer the proposition , and the proposition can also infer the proposition .

思路:

  题目要求的点对数只要求出强连通分量就能得到, 但是因为题目给出的连边方式过于诡异,在最坏情况下边数能达到 ,所以要想办法优化连边的过程。
  假设题目的连边方式是给定一个序列,每次对一个区间连边。可以用线段树维护序列,线段树上的每个点都向儿子连边,叶子就是实际的点。这样每次连边就能像区间查询一样对 个结点连边了。(这应该就是线段树优化连边?可能是我孤陋寡闻,这段是我乱搞出来的.....
  再把这个操作搬到树上,既然要同时维护子树和深度,可以考虑在 dfs 的过程中做线段树(维护深度)合并。因为不能破坏原来的连边,所以还要可持久化。这样连出的边就是 的了。复杂度
  ps:因为栈空间的问题,这段代码得用C++交。

代码:

#include <cstdio>
#include <cstring>
#pragma comment(linker, "/STACK:102400000,102400000")
#define mset(a, b) memset(a, b, sizeof a)
#define rep(i, a, b) for(int i(a), i##_END_(b); i <= i##_END_; ++i)
#define drep(i, a, b) for(int i(a), i##_END_(b); i >= i##_END_; --i)
using namespace std;
typedef long long ll;
template<class T> inline bool tomax(T &a, T b) {return a < b ? a = b, 1 : 0;}
template<class T> inline bool tomin(T &a, T b) {return b < a ? a = b, 1 : 0;}
const int N = 100005, M = N * 80;

template<int N, int M, class T> struct Link {
#define erep(k, G, o) for(int k = G.HEAD[o]; k; k = G.NXT[k])
    int HEAD[N], NXT[M], tot; T W[M];
    void clear() {tot = 0; mset(HEAD, 0);}
    void add(int x, T w) {NXT[++tot] = HEAD[x]; W[HEAD[x] = tot] = w;}
    T& operator[] (int x) {return W[x];}
};
Link<M, M, int> G;
Link<N, N, int> T;

int ls[M], rs[M];
int tot;
int newNode() {
    int o = ++tot;
    ls[o] = rs[o] = 0;
    return o;
}
#define mid ((L + R) >> 1)
#define lson ls[o], L, mid
#define rson rs[o], mid + 1, R
void build(int x, int a, int &o, int L, int R) {
    if(L == R) {
        o = a;
        ls[o] = rs[o] = 0;
        return;
    }
    o = newNode();
    if(x <= mid) build(x, a, lson), G.add(o, ls[o]);
    else build(x, a, rson), G.add(o, rs[o]);
}
int merge(int u, int v, int L, int R) {
    if(!u && !v) return 0;
    int o = newNode();
    if(L == R) {
        if(u) G.add(o, u);
        if(v) G.add(o, v);
        return o;
    }
    if(!u || !v) {
        int p = u | v;
        ls[o] = ls[p];
        rs[o] = rs[p];
        G.add(o, p);
    }
    else {
        ls[o] = merge(ls[u], ls[v], L, mid);
        rs[o] = merge(rs[u], rs[v], mid + 1, R);
        if(ls[o]) G.add(o, ls[o]);
        if(rs[o]) G.add(o, rs[o]);
    }
    return o;
}
void link(int l, int r, int x, int o, int L, int R) {
    if(!o) return;
    if(l == L && r == R) {
        G.add(x, o);
        return;
    }
    if(r <= mid) link(l, r, x, lson);
    else if(l > mid) link(l, r, x, rson);
    else link(l, mid, x, lson), link(mid + 1, r, x, rson);
}

int rt[N], dep[N], n;
void dfs(int o, int d) {
    build(dep[o] = d, o, rt[o], 1, n);
    erep(k, T, o) {
        int v = T[k];
        dfs(v, d + 1);
        rt[o] = merge(rt[o], rt[v], 1, n);
    }
}

int val[M], stk[M], bel[M], cnt[M], dfn[M], low[M], top, cur, bcnt;
void tarjan(int o) {
    dfn[o] = low[o] = ++cur;
    stk[++top] = o;
    erep(k, G, o) {
        int v = G[k];
        if(!dfn[v]) {
            tarjan(v);
            tomin(low[o], low[v]);
        }
        else if(!bel[v]) tomin(low[o], dfn[v]);
    }
    if(low[o] == dfn[o]) {
        cnt[++bcnt] = 0;
        do {
            cnt[bcnt] += val[stk[top]];
            bel[stk[top]] = bcnt;
        } while(stk[top--] != o);
    }
}

int main() {
    int cas;
    scanf("%d", &cas);
    while(cas--) {
        G.clear(); T.clear();
        scanf("%d", &n);
        rep(i, 2, n) {
            int f;
            scanf("%d", &f);
            T.add(f, i);
        }
        tot = n;
        dfs(1, 1);
        mset(val, 0); mset(dfn, 0); mset(bel, 0);
        rep(i, 1, n) {
            int x, d;
            scanf("%d%d", &x, &d);
            link(dep[x], dep[x] + d, i, rt[x], 1, n);
            val[i] = 1;
        }
        cur = bcnt = 0;
        rep(i, 1, tot)
            if(!dfn[i]) tarjan(i);
        ll ans = 0;
        rep(i, 1, bcnt) 
            ans += (ll) cnt[i] * (cnt[i] - 1) / 2;
        printf("%lld\n", ans);
    }
    return 0;
}