P5314 [Ynoi2011] ODT

好题，牛牛的一个套路。

先树剖一下，我们可以很简单的用树状数组维护每个点的真实值。

对于每个点只维护所有轻儿子的信息，对于每次询问的时候暴力加入当前点，重儿子以及父亲的信息，查询第 \(k\) 大，再删除信息即可。

考虑链修改的影响。因为只维护的是轻儿子的信息，那么只有链上的所有轻边会修改。

具体的，设当前轻边 \((x,y)\)，\(y\) 是父亲，先在 \(y\) 中删除原来 \(x\) 的信息，再加入当前 \(x\) 的真实信息即可。

树剖链查询的时候只会经过 \(O(\log n)\) 的轻边，用平衡树维护每个点的信息即可，直接用 pb_ds 就好了！

默认 \(n,m\) 同阶，复杂度 \(O(n \log^2 n)\)。

小细节：树剖最后链修改 \(x,y\) 跳到一条重链时，如果一端是重链头，需要对它的父亲进行修改。

#include<bits/stdc++.h>
using namespace std;
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

typedef long long ll;
const int N=1e6+3;
int n,m,a[N];
vector<int>ve[N];
struct Nod
{
	int x,id;
	friend bool operator <(Nod a,Nod b){return a.x!=b.x?a.x<b.x:a.id<b.id;}
};
tree<Nod,null_type,less<Nod>,rb_tree_tag,tree_order_statistics_node_update>tr[N];
struct BIT
{
	int tr[N];
	void Add(int x,int y){for(;x<=n;x+=x&-x)tr[x]+=y;}
	int Ask(int x){int s=0;for(;x;x-=x&-x)s+=tr[x];return s;}
	void Mdf(int l,int r,int d){Add(l,d);Add(r+1,-d);}
}T;
struct ShuPou
{
	int sz[N],fa[N],dep[N],hson[N],tim,top[N],dfn[N],pos[N];
	void Dfs1(int x)
	{
		sz[x]=1;dep[x]=dep[fa[x]]+1;
		for(int y:ve[x])if(y!=fa[x])
		{
			fa[y]=x;Dfs1(y);sz[x]+=sz[y];
			if(sz[hson[x]]<sz[y])hson[x]=y;
		}
	}
	void Dfs2(int x,int tp)
	{
		top[x]=tp;pos[x]=++tim;dfn[tim]=x;T.Mdf(tim,tim,a[x]);
		if(hson[x])Dfs2(hson[x],tp);
		for(int y:ve[x])if(y!=fa[x]&&y!=hson[x])Dfs2(y,y),tr[x].insert({a[y],y});
	}
	void Upd(int x,int y,int z)
	{
		while(top[x]!=top[y])
		{
			if(dep[top[x]]<dep[top[y]])swap(x,y);
			int tp=top[x];tr[fa[tp]].erase({a[tp],tp});
			T.Mdf(pos[tp],pos[x],z);a[tp]=T.Ask(pos[tp]);
			tr[fa[tp]].insert({a[tp],tp});x=fa[top[x]];
		}
		if(dep[x]<dep[y])swap(x,y);
		if(dep[y]!=dep[top[y]]||!fa[y]){T.Mdf(pos[y],pos[x],z);return;}
		tr[fa[y]].erase({a[y],y});T.Mdf(pos[y],pos[x],z);
		a[y]=T.Ask(pos[y]);tr[fa[y]].insert({a[y],y});
	}
}Sp;
void Add(int x,int y){if(y)tr[x].insert({T.Ask(Sp.pos[y]),y});}
void Del(int x,int y){if(y)tr[x].erase({T.Ask(Sp.pos[y]),y});}
int main()
{
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0); 
	cin>>n>>m;
	for(int i=1;i<=n;i++)cin>>a[i];
	for(int i=1,x,y;i<n;i++)cin>>x>>y,ve[x].push_back(y),ve[y].push_back(x);
	Sp.Dfs1(1);Sp.Dfs2(1,1);
	while(m--)
	{
		int op,x,y,z;cin>>op>>x>>y;
		if(op==1){cin>>z;Sp.Upd(x,y,z);continue;}
		Add(x,x);Add(x,Sp.hson[x]);Add(x,Sp.fa[x]);
		cout<<tr[x].find_by_order(y-1)->x<<'\n';
		Del(x,x);Del(x,Sp.hson[x]);Del(x,Sp.fa[x]);
	}
}

有任何疑惑欢迎与我交流。