题目链接：[Ynoi2008] stcm

题意：

给定一棵树，可以维护一个集合，支持以下操作：

  1. 当前集合中插入一个节点 $x$。
  2. 撤回上一次插入操作。
  3. 将当前点集标为第 $i$ 个点的子树补信息。

一个点 $x$ 的子树补信息定义为：树的点集除去 $x$ 的子树（包括 $x$）内的点得到的集合。
要求在 $4.5\times 10^6$ 次操作以内，标记所有点的子树补。
$1\le T\le 3,1\le n\le 10^5$。

操作次数是 $\mathcal{O}(n\log n)$ 级别，先无脑重链剖分一下。

根据重链剖分相关结论，可知轻子树大小总和是 $\mathcal{O}(n\log n)$ 的。因此，对于一条重链上的所有节点，我们可以直接暴力加入所有轻子树，这样每一棵轻子树只被加入一次。

具体来说，对于一条重链的顶端 $x$，假设当前状态已经是 $x$ 的子树补，则每次可以暴力将 $x$ 的轻儿子遍历一遍，加入所有节点，再加入 $x$，得到 $x$ 的重儿子的子树补。

则现在的问题变成了，如何求出每一条重链顶端的子树补。

对于一条重链的顶端 $x$，假设当前状态已经是 $x$ 的子树补，当我们进行一些操作之后，当前状态转变为 $x$ 这条重链上某一个节点 $y$ 的某一个轻儿子 $p$ 的子树补，则我们就可以递归处理 $p$ 子树内部的答案了。

若要让当前 $x$ 的子树补，转变为 $p$ 的子树补，则 $x$ 这条重链上其他节点的所有轻儿子都要被标记，所需要的操作次数是：

$$ \sum_{y\in \text{link}(x)}\sum_{k\in \text{lightson}(y),k\ne p}\text{siz}(k) $$

的级别。我们希望这个式子的总和尽量小。

考虑把所有轻子树 $k$ 看作一个二元组 $(k,\text{siz}(k))$，重链上的点 $y$ 看作 $(y,1)$。建立这样一个二元组的哈夫曼树，可知一棵权值和为 $s$ 的哈夫曼树，带权子树和是 $\mathcal{O}(s\log s)$ 级别的。

于是，可以在哈夫曼树上 $\text{DFS}$，每次要往哈夫曼树的左子树进行处理，就暴力加入右子树内的所有节点；要往右子树走，就加入左子树节点。

这样的时间复杂度看起来是 $\mathcal{O}(n\log^2 n)$ 的，但是好像可以通过将每次递归子问题所得到的哈夫曼树拼接起来，最后得到一个 $\mathcal{O}(n\log n)$ 的时间复杂度。

//Code By CXY07
#include<bits/stdc++.h>
using namespace std;

//#define FILE
//#define int long long
#define file(FILENAME) freopen(FILENAME".in", "r", stdin), freopen(FILENAME".out", "w", stdout)
#define randint(l, r) (rand() % ((r) - (l) + 1) + (l))
#define LINE() cout << "LINE = " << __LINE__ << endl
#define debug(x) cout << #x << " = " << x << endl
#define abs(x) ((x) < 0 ? (-(x)) : (x))
#define popc(x) __builtin_popcount(x)
#define inv(x) qpow((x), mod - 2)
#define lowbit(x) ((x) & (-(x)))
#define ull unsigned long long
#define pii pair<int, int>
#define LL long long
#define mp make_pair
#define pb push_back
#define scd second
#define vec vector
#define fst first
#define endl '\n'

const int MAXN = 1e5 + 10;
const int INF = 2e9;
const double eps = 1e-6;
const double PI = acos(-1);
//const int mod = 1e9 + 7;
//const int mod = 998244353;
//const int G = 3;
//const int base = 131;

int T, n, m, cnt, opt_cnt;
int fa[MAXN], siz[MAXN], son[MAXN];
int huffman[MAXN * 50][2], hc, id[MAXN * 50];
int type[MAXN * 50];
vec<int> G[MAXN];
priority_queue<pii> Q;

template<typename T> inline bool read(T &a) {
    a = 0; char c = getchar(); int f = 1;
    while(c < '0' || c > '9') { if(c == '-') f = -1; c = getchar(); }
    while(c >= '0' && c <= '9') { a = a * 10 + (c ^ 48); c = getchar(); }
    return a *= f, true;
}

template<typename A, typename ...B>
inline bool read(A &x, B &...y) { return read(x) && read(y...); }

void DFS(int x) {
    siz[x] = 1;
    for(auto to : G[x]) {
        DFS(to), siz[x] += siz[to];
        if(!son[x] || siz[son[x]] < siz[to]) son[x] = to;
    }
}

void calc(int x);

void clear() {
    hc = opt_cnt = 0;
    for(int i = 1; i <= n; ++i) G[i].clear();
    memset(huffman, 0, sizeof huffman);
    memset(type, 0, sizeof type);
    memset(id, 0, sizeof id);
    memset(son, 0, sizeof son);
}

void add(int x) { printf("+%d", x); ++cnt; opt_cnt++; }

void pop() { putchar('-'); cnt--; opt_cnt++; }

void eq(int x) { printf("=%d", x); opt_cnt++; }

void roll(int x) { assert(cnt >= x); while(cnt > x) pop(); }

void add_son(int x) { add(x); for(auto to : G[x]) add_son(to); }

void add_Huffman(int x) {
    if(!huffman[x][0] || !huffman[x][1]) {
        if(type[x] == 1) add(id[x]);
        else add_son(id[x]);
        return;
    }
    add_Huffman(huffman[x][0]), add_Huffman(huffman[x][1]);
}

void DFS_Huffman(int x) {
    if(!huffman[x][0] || !huffman[x][1]) {
        if(type[x] == 2) calc(id[x]);
        return;
    }
    int cur = cnt;
    add_Huffman(huffman[x][1]); DFS_Huffman(huffman[x][0]); roll(cur);
    add_Huffman(huffman[x][0]); DFS_Huffman(huffman[x][1]); roll(cur);
}

void calc(int x) {
    int cur = cnt, now = x;
    while(now) {
        eq(now); Q.push(mp(-1, ++hc));
           id[hc] = now, type[hc] = 1; add(now); 
        for(auto to : G[now]) 
            if(to != son[now]) {
                add_son(to); 
                Q.push(mp(-siz[to], ++hc)); id[hc] = to, type[hc] = 2; 
            }
        now = son[now];
    }
    roll(cur);
    while(Q.size() > 1) {
        pii x, y; x = Q.top(); Q.pop(); y = Q.top(); Q.pop();
        Q.push(mp(x.fst + y.fst, ++hc)); 
        huffman[hc][0] = x.scd, huffman[hc][1] = y.scd;
    } Q.pop();
       DFS_Huffman(hc); roll(cur);
}

void solve() {
    clear();
    for(int i = 2; i <= n; ++i) read(fa[i]), G[fa[i]].pb(i);
    DFS(1); calc(1); putchar('!'); putchar('\n'); assert(!cnt);
}

signed main () {
#ifdef FILE
    freopen("P7124.in", "r", stdin);
    freopen("P7124.out", "w", stdout);
#endif
    while(scanf("%d", &n) != EOF) solve();
    return 0;
}

标签: 重链剖分, Huffman树

添加新评论