Luogu P2495 [SDOI2011]消耗战

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
inline bool cmp(int a, int b) {
    return nddfs[a] < nddfs[b];
}
int cntkey, key[MAXn + 10];
int cntuse, use[MAXn + 10];
int top, stk[MAXn + 10];
void InitAdj() {
    while (cntuse) {
        l2.head[use[cntuse--]] = 0;
    }
    l2.cntnex = 0;
}
void EvaVirTree() {
    InitAdj();
    sort(key + 1, key + 1 + cntkey, cmp);
    stk[++top] = 1;
    use[++cntuse] = 1;
    for (int i = 1; i <= cntkey; ++i) {
        int lca = Lca(key[i], stk[top]);
        for (int j = top; j; --j) {
            if (nddfs[stk[j]] <= nddfs[lca]) {
                for (; top > j + 1; --top) {
                    Insert(stk[top - 1], stk[top]);
                }
                if (top == j + 1) {
                    Insert(lca, stk[top]);
                    --top;
                }
                if (stk[j] != lca) {
                    stk[++top] = lca;
                    use[++cntuse] = lca;
                }
                stk[++top] = key[i];
                use[++cntuse] = key[i];
                break;
            }
        }
    }
    for (; top > 1; --top) {
        Insert(stk[top - 1], stk[top]);
    }
    --top;
}