【UOJ#53】【UR#4】追击圣诞老人
树链剖分，堆
题目大意：
给定一棵 $n$ 个点的树，每个点有正的点权 $w_i$。
定义一条路径 $(p_1,p_2,p_3,\ldots,p_l)$ 的代价为 $\sum\limits_{i=1}^l w_{p_i}$。
对于一个点 $u$，有参数 $a_u,b_u,c_u$，只有树上处于 $a_u,b_u,c_u$ 三个点两两最短路上的点才是 $u$ 能到达的点。
问代价前 $k$ 小的路径的代价。
空间限制较紧。
题解：
不难想到用堆维护路径的代价，每次取出最小的那个，并在此基础上加以扩展后再放入堆里。这样取出来的前 $k$ 个即为答案。
但是一个点能到的点的个数是很多的，肯定不能把所有转移都放进堆里。
对于一个关于点 $u$ 的状态的后继状态，我们一定是先取出它能转移到的点中 $w_i$ 最小的那个，然后是次小的，依此类推。我们希望只将 $u$ 后继状态的最小状态放入堆中，等取出的时候再考虑把次小的状态加入，等等。
考虑 $u$ 能到的点是一条链的情况。对于链 $(a,b)$，其 $w$ 最小的点是 $k$，我们在选了 $k$ 之后，可以将 $(a,b)$ 变成 $(a,k)$ 和 $(b,k)$ 两条链（不含 $k$ 这个端点），然后在两条链中分别找最小值再插入堆中。这样一个状态取出时，新加入的状态是 $O(1)$ 的。
现在 $u$ 能到的点是包含其中三个点的连通块，我们可以简单地将其分成三条链来处理。
为了使计算过程简便，可以将链都拆成从下往上的（即 $(a,b)$ 满足其中一个端点是另一个端点的祖先）。
那么接下来就是要求链上的最值问题了。由于本题的数据范围以及时空限制，倍增、ST 表的空间复杂度无法接受。因此考虑树链剖分。
这里如果对每段链都进行线段树询问，则时间复杂度为 $O(k\log^2 n)$，难以通过。注意到除了最后一段，我们每次跳重链的时候都是跳了这段重链的一个前缀。因此对每个重链的前缀记录一下最小的那个点，然后中间这部分就可以单次 $O(1)$ 了。最后那段用线段树即可。
时间复杂度 $O((n+k)\log n)$。空间复杂度 $O(n+k)$。
Code：
#include<iostream>
#include<algorithm>
#include<queue>
#include<utility>
using namespace std;
const int N=5e5+5;
int n,k,w[N],fa[N],head[N],nxt[N],mn[N];
pair<int,int>A[N][3];
int sz[N],son[N],dep[N],top[N],dfn[N],idx,idfn[N];
int _mn[N<<2];
inline int _min(int a,int b){return w[a]<w[b]?a:b;}
void dfs(int now){
sz[now]=1;
for(int to=head[now];to;to=nxt[to]){
dep[to]=dep[now]+1;
dfs(to);
sz[now]+=sz[to];
if(!son[now]||sz[son[now]]<sz[to])son[now]=to;
}
}
void dfs2(int now){
idfn[dfn[now]=++idx]=now;
if(son[now])top[son[now]]=top[now],mn[son[now]]=_min(mn[now],son[now]),dfs2(son[now]);
for(int to=head[now];to;to=nxt[to])if(to!=son[now])top[to]=mn[to]=to,dfs2(to);
}
inline int LCA(int x,int y){
while(top[x]!=top[y])if(dep[top[x]]>dep[top[y]])x=fa[top[x]];else y=fa[top[y]];
return dep[x]<dep[y]?x:y;
}
void build(int l,int r,int o){
if(l==r)_mn[o]=idfn[l];else{
const int mid=(l+r)/2;
build(l,mid,o<<1),build(mid+1,r,o<<1|1);
_mn[o]=_min(_mn[o<<1],_mn[o<<1|1]);
}
}
int query(int l,int r,int o,const int&L,const int&R){
if(L<=l&&r<=R)return _mn[o];
const int mid=(l+r)/2;
if(L<=mid&&mid<R)return _min(query(l,mid,o<<1,L,R),query(mid+1,r,o<<1|1,L,R));
if(L<=mid)return query(l,mid,o<<1,L,R);
return query(mid+1,r,o<<1|1,L,R);
}
struct data{
int u,x,y,d;
inline bool operator<(const data&rhs)const{return d>rhs.d;}
};
priority_queue<data>q;
void update(int u,int x,int y,int s){
if(dep[x]>=dep[y])return;
int id=0;
int v=y;
while(top[v]!=top[x]){
id=_min(id,mn[v]);
v=fa[top[v]];
}
if(v!=x)id=_min(id,query(1,n,1,dfn[x]+1,dfn[v]));
if(s+w[id]>1e8)return;
q.push((data){id,x,y,s+w[id]});
}
inline void rebuild(){
priority_queue<data>p;
for(int i=0;i<k;++i)p.push(q.top()),q.pop();
q=p;
}
void work(){
for(int i=1;i<=n;++i)q.push((data){i,i,i,w[i]});
for(int T=1;T<=k;++T){
data dt=q.top();q.pop();
int u=dt.u,d=dt.d;
cout<<d<<'\n';
update(u,dt.x,fa[u],d-w[u]);
update(u,u,dt.y,d-w[u]);
update(u,A[u][0].first,A[u][0].second,d);
update(u,A[u][1].first,A[u][1].second,d);
update(u,A[u][2].first,A[u][2].second,d);
if((int)q.size()>3*k)rebuild();
}
}
int main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>n>>k;
for(int i=1;i<=n;++i)cin>>w[i];w[0]=1e9;
for(int i=2;i<=n;++i)cin>>fa[i],nxt[i]=head[fa[i]],head[fa[i]]=i;
dfs(dep[1]=1),dfs2(mn[1]=top[1]=1);
for(int i=1;i<=n;++i){
int a,b,c;
cin>>a>>b>>c;
int ab=LCA(a,b),ac=LCA(a,c),bc=LCA(b,c);
if(dep[ab]<=dep[ac]&&dep[ab]<=dep[bc]){
A[i][0]=make_pair(ab,a),A[i][1]=make_pair(fa[ab],b);
A[i][2]=make_pair((dep[ac]>dep[bc]?ac:bc),c);
}else if(dep[ac]<=dep[ab]&&dep[ac]<=dep[bc]){
A[i][0]=make_pair(ac,a),A[i][1]=make_pair(fa[ac],c);
A[i][2]=make_pair((dep[ab]>dep[bc]?ab:bc),b);
}else if(dep[bc]<=dep[ab]&&dep[bc]<=dep[ac]){
A[i][0]=make_pair(bc,b),A[i][1]=make_pair(fa[bc],c);
A[i][2]=make_pair((dep[ab]>dep[ac]?ab:ac),a);
}else exit(1);
}
build(1,n,1);
work();
return 0;
}