[DS记录]P7124 [Ynoi2008] stcm

**题意** ： 给定一棵树，你可以维护一个集合 $S$，支持三种操作： 1. 将 $S$ 中插入一个节点 $x$ 2. 撤回上一次插入操作 3. 将 $S$ 标为第 $i$ 个点的子树补信息 一个点 $x$ 的子树补信息定义为，树的点集除去 $x$ 的子树（包括 $x$）内的点得到的集合。 需要得到每个点的子树补信息。 1 操作的次数限制为 $4.5\times 10^6$ 次。 多组数据， $T\leq 3,n\leq 10^5$ ，时限$\texttt{1s}$。 ------------ 根据数据范围，最终使用的操作次数应是 $O(n\log n)$ 级别的。 - 菊花图 等价于构造单独缺每个点的集合。 建立一棵线段树，并遍历。走向左儿子时，将右侧加入集合。走向右儿子时，将左侧加入集合。 这样，走到叶节点时，所得的集合就是缺少该点的集合。 每个数会被加入“线段树上深度”次，于是操作数为 $O(n\log n)$。 - 一般情况 将树轻重链剖分。 对于每条重链，首先 $S$ 是重链顶的子树补信息，然后一路加入轻子树。 轻边子树大小和是 $O(n\log n)$ 的。 接下来的问题是如何得到轻儿子的子树补信息。 取出重链上挂着的所有轻子树，问题又转化为类似菊花图的情况。  根据 HLD 的结论，根据轻儿子的大小建哈夫曼树即可让总复杂度为 $O(n\log n)$。 ```cpp #include<algorithm> #include<cstring> #include<cstdio> #include<vector> #include<queue> #define Pr pair<int,int> #define fir first #define sec second #define mkp make_pair #define MaxN 100500 using namespace std; namespace FastOutput { char obuf[8000500],*O=obuf; void putc(char ch){*O++=ch;} void print(int x){if(x>9)print(x/10);*O++=x%10+'0';} void flush(bool op=0){if (O-obuf>=8000000||op){fwrite(obuf,O-obuf,1,stdout);O=obuf;}} }using namespace FastOutput; int tim; void find(int u){putc('=');print(u);flush();} void add(int u){tim++;putc('+');print(u);flush();} void del(){tim--;putc('-');flush();} vector<int> g[MaxN]; int siz[MaxN],mp[MaxN]; void pfs1(int u) { siz[u]=1; for (int i=0,v;i<g[u].size();i++) if (!siz[v=g[u][i]]){ pfs1(v); siz[u]+=siz[v]; if (siz[mp[u]]<siz[v]) mp[u]=v; } } void dfs2(int u) { add(u); for (int i=0;i<g[u].size();i++) dfs2(g[u][i]); } struct Node{int l,r;}a[MaxN<<1]; void dfs4(int u){ if (!a[u].l){dfs2(u);return ;} dfs4(a[u].l);dfs4(a[u].r); } void dfs(int u); void dfs3(int u) { if (!a[u].l){dfs(u);return ;} int sav=tim; dfs4(a[u].r);dfs3(a[u].l); while(tim>sav)del(); dfs4(a[u].l);dfs3(a[u].r); while(tim>sav)del(); } int tot; priority_queue<Pr> q; int st[MaxN],st2[MaxN],tn,tn2; void dfs(int u) { tn=0;tn2=0; for (int p=u;p;p=mp[p])st[++tn]=p; int sav=tim; for (int i=1;i<=tn;i++){ int p=st[i];find(p); for (int i=0,v;i<g[p].size();i++) if ((v=g[p][i])!=mp[p])dfs2(st2[++tn2]=v); add(p); }while(tim>sav)del(); if (!tn2)return ; for (int i=1;i<=tn;i++)add(st[i]); for (int i=1;i<=tn2;i++) q.push(mkp(-siz[st2[i]],st2[i])); while(q.size()>1){ Pr u1=q.top();q.pop(); Pr u2=q.top();q.pop(); a[++tot]=(Node){u1.sec,u2.sec}; q.push(mkp(u1.fir+u2.fir,tot)); }int rt=q.top().sec;q.pop(); dfs3(rt); while(tim>sav)del(); } int n; void solve() { tot=n; for (int i=2,fa;i<=n;i++){ scanf("%d",&fa); g[fa].push_back(i); }pfs1(1); dfs(1);putc('!');putc('\n'); memset(a,0,sizeof(Node)*(tot+3)); for (int i=1;i<=n;i++){ siz[i]=mp[i]=0; g[i].clear(); } } int main() { while(~scanf("%d",&n))solve(); flush(1); return 0; } ```