题解 CF860E 【Arkady and a Nobody-men】
SIGSEGV
2020-03-09 20:40:59
长链剖分的玄学题目。重链剖分要$O(N\log^2 N)$的时间复杂度,LCA+单调栈也要$O(N\log N)$。但是长链剖分珂以$O(N)$。
具体做法:
观察到$ans_v=ans_{fa(v)}+dep_{fa(v)}+ans'_v$，其中$dep$为深度(根的深度为1)，$ans$为答案，$ans'_v$为除了$v$外所有深度为$dep_v$的点对$v$产生的贡献。$dep_v$在这个柿子中的含义是$v$的所有祖先(不包含自己)。
不妨令`dfs(v)`返回一个vector,其中vector的第$d$项是一个三元组$(ans'_x,x,cnt_x)$，分别表示仅考虑$x$在$v$的子树内的$dep$相同的点时的$ans'_x$,子树内深度为$d$的任意一点$x$和子树内深度为$d$的点的个数。
考虑怎么合并$v$的两个儿子的vector。显然对应的深度的三元组才能合并。然后考虑如何合并$(ans'_x,x,cnt_x)$和$(ans'_y,y,cnt_y)$。我们只要令$ans'_x+=dep_v\times cnt_y$,$ans'_y+=dep_v\times cnt_x$,然后返回$(ans'_x,x,cnt_x+cnt_y)$。但是这个$ans'_y$的值显然不能扔着不管。观察到接下来的过程中所有$dep$与$x$,$y$相同的点都会同时对$ans'_x$和$ans'_y$产生贡献，也就是$ans'_y-ans'_x$的值已经确定。在一张新图上从$x$向$y$连一条边权为$ans'_y-ans'_x$的边即可，最后结束后珂以用这张图还原。
在实现时，因为$v$的vector的第$d$项在$d< dep_v$时都是无意义的，所以珂以用一种支持`push_front`操作的数据结构(邻接表）代替vector。
要跑四遍dfs...(第一遍LPD,第二遍如上，第三遍还原$ans'$,第四步计算$ans$)
```cpp
#include <bits/stdc++.h>
using namespace std;
const int N = 500005;
using ll = long long;
int n;ll ans[N];
vector<int> e[N];
vector<pair<int,int>> g[N];
int a[N],dep[N],lson[N],lv[N];
int head[N],v[N],w[N],nxt[N],ptr;
inline void add_edge(int uu,int vv,int ww)
{v[ptr] = vv;w[ptr] = ww;nxt[ptr] = head[uu];head[uu] = ptr++;}
void dfs1(int pos)
{
for (auto &i : e[pos])
{
dep[i] = dep[pos] + 1;dfs1(i);
if (lv[pos] < lv[i] + 1) lson[pos] = i,lv[pos] = lv[i] + 1;
}
}
void dfs2(int pos)
{
if (lson[pos]) dfs2(lson[pos]),head[pos] = head[lson[pos]];
for (auto &i : e[pos])
{
if (i == lson[pos]) continue;
dfs2(i);
int j = head[pos],k = head[i];
while (k != -1)
{
ans[w[k]] += dep[pos] * v[j];ans[w[j]] += dep[pos] * v[k];
g[w[j]].push_back({w[k],ans[w[k]] - ans[w[j]]});v[j] += v[k];
j = nxt[j];k = nxt[k];
}
}
add_edge(pos,1,pos);
}
void dfs3(int pos,bool rt = 1)
{
if (rt && lson[pos]) dfs3(lson[pos]);
for (auto &i : g[pos]) ans[i.first] = ans[pos] + i.second,dfs3(i.first,0);
}
void dfs4(int pos)
{
for (auto &i : e[pos]) ans[i] += dep[pos] + ans[pos],dfs4(i);
}
int main ()
{
ios::sync_with_stdio(false);
cin >> n;int t1,rt = 0;
for (int i = 1;i <= n;i++)
{
cin >> t1;if (t1) e[t1].push_back(i);else rt = i;
}
memset(head,-1,sizeof(head));memset(nxt,-1,sizeof(nxt));
dep[rt] = 1;dfs1(rt);dfs2(rt);dfs3(rt);dfs4(rt);
for (int i = 1;i <= n;i++) cout << ans[i] << ' ';
return 0;
}
```