H 戏团演出

思路

听说这题是原题？

虽然效率更低但还是介绍一个现场口胡的树剖+区间差分做法：

先考虑解决一维区间上的覆盖问题：对于一个起点为 $ll$，终点为 $rr$，颜色为 $ww$ 的区间，我们可以在 $ll$ 处打上让 $ww$ 加一的标记，同时在 $r+1r+1$ 处打上让 $ww$ 减一的标记，最后从 $11$ 到 $nn$ 按顺序扫一遍，每次操作后在优先队列里更新最优答案。

接下来解决树上问题：考虑树剖后每条链最多被分解成 $O(log)O(log)$ 条重链，而每条重链对应一个连续区间，于是我们可以把每个询问拆分成 $O(log)O(log)$ 个连续区间，然后搬到平面上处理。

时间复杂度 $O(nlo{g}^{2}n)O(nlog^2n)$。

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int i,j,k,n,m,t,son[100500],sz[100500],tp[100500],dep[100500],fa[100500],id[100500],it,w,res[100500],id2[100500],it2;
int cur[100500];
vector<int> v[100500];
vector<pair<int,int> >op[100500];

void dfs0(int x,int f){
	sz[x]++;
	fa[x]=f;
	for(auto i:v[x])if(i!=f){
		dep[i]=dep[x]+1;
		dfs0(i,x);
		sz[x]+=sz[i];
		if(sz[i]>=sz[son[x]])son[x]=i;
	}
}
void dfs1(int x,int fa,int t){
	tp[x]=t;
	id[x]=++it;
	id2[it]=x;
	if(son[x])dfs1(son[x],x,t);
	for(auto i:v[x])if(i!=fa&&i!=son[x]){
		dfs1(i,x,i);
	}
}

void add(int l,int r,int w){
	op[l].push_back({w,1});
	op[r+1].push_back({w,-1});
}

map<int,int> F;
int F2[2005000];

void fuk(int x,int y,int w){
	if(!F[w]){
		F[w]=++it2;
		F2[it2]=w;
	}
	w=F[w];
	while(tp[x]!=tp[y]){
		if(dep[tp[x]]>dep[tp[y]]){
			add(id[tp[x]],id[x],w);
			x=fa[tp[x]];
		}
		else{
			add(id[tp[y]],id[y],w);
			y=fa[tp[y]];
		}
	}
	if(dep[y]<dep[x])swap(x,y);
	add(id[x],id[y],w);
	return;
}

int main() {
    ios::sync_with_stdio(0);
    cin>>n>>t;
    for(i=1;i<n;i++){
    	cin>>j>>k;
    	v[j].push_back(k);
    	v[k].push_back(j);
	}
	dfs0(1,1);
	dfs1(1,1,1);
	while(t--){
		cin>>j>>k>>w;
		fuk(j,k,w);
	}
	priority_queue<tuple<int,int,int> >q;
	for(i=1;i<=n;i++){
		for(auto [j,k]:op[i]){
			cur[j]+=k;
			q.push({cur[j],-F2[j],j});
		}
		while(!q.empty()){
			auto [x,y,z]=q.top();
			y=-y;
			if(cur[z]!=x){
				q.pop();
				continue;
			}
			if(!x)break;
			res[id2[i]]=y;break;
		}
	}
	for(i=1;i<=n;i++){
		cout<<res[i]<<'\n';
	}
}