自动搬运

查看原文

来自洛谷，原作者为

	harmis_yz beiribaol，幻想，永恒。

搬运于2025-08-24 23:05:08，当前版本为作者最后更新于2025-07-02 15:07:27，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

莫名其妙的题。

分析

首先这题不需要求没有修改时 $u$ 变成根的时间。要求的话大概是发现对于 $u$ 变到 $fa_u$ 所需的时间是它其它兄弟节点为根的子树中前缀最小值不小于 $val_u$ 的链的数量，然后处理一下。

但是这题需要我们让 $u$ 变到根的时间最短，那么这个时间一定是 $dep_u$。因为我们存在答案上界是将 $P(1,u)$ 全部修改成 $inf$，此时在 $u$ 变成根以前是不会选择其它节点的。模拟一下发现可能会影响到 $u$ 变成根的时间的点只会是 $u$ 到 $1$ 路径上所有点 $x_i$ 的兄弟节点。只要存在一种修改方式，使得路径任意一个前缀，都满足 $val_{x_i}> mx_{x_i}$ 就行了。其中 $mx_{x_i}$ 是 $x_i$ 到 $1$ 路径上所有点的兄弟节点中最大的价值。

定义状态函数 $f_u$ 表示让 $u$ 满足条件的最小代价。那么一定有 $f_v \in \{f_u,f_{u}+1\}[v\in son_u]$。那么对于 $v$ 来说，$f_v=f_u+1$ 一定是当前前缀路径上存在至少一个点 $x$ 的兄弟节点 $y$，满足 $val_y \ge val_v$。则对于 $v$ 来说，我们可以选择将 $val_v$ 变成 $inf$，对于 $v$ 的子树来说，可以选择将 $val_v$ 变成 $inf$ 或将 $val_y$ 变成 $0$。

如果 $val_y\ge val_v$ 的数量为 $1$。则可看作将 $val_v$ 变成 $inf$ 或将 $val_y$ 变成 $0$，此时将 $val_y$ 变成 $0$ 更优。

如果 $val_y \ge val_v$ 的数量大于 $1$。若 $v$ 子树点的最优策略均为 $val_w$ 变成 $inf$，则变不变 $val_y$ 无所谓。若存在 $w$ 的最优策略为删点，当 $val_w \le val_v$ 时，删的点要么是 $y$ 中的一个，要么是 $w$ 到 $v$ 路径上点的兄弟节点中的一个，后者和 $v$ 无关。当 $val_v < val_w$ 时，如果将 $val_y$ 变成 $0$，且满足 $val_y \ge val_w$，此时不劣。如果变成 $0$ 的点满足 $val_y < val_w$，那么支持 $w$ 的前提是将 $val_v$ 变成 $inf$，此时 $y$ 的变化可以看作将 $val_v$ 变成 $inf$，无影响。

把上面的情况取交集，发现我们可以改变第一个满足 $val_y \ge val_v$ 的点。

那么现在需要实现：快速加点或删点，快速查询第一个比 $x$ 大的数的值，快速查询比 $x$ 大的数的数量。可以任意维护，时间复杂度 $O(n\log n+q)$。

我说的是不是莫名奇妙的。

代码

const int N=1e6+10;
int n,q;
int val[N],f[N];
vector<int> e[N];
multiset<int> st;

il void dfs(int u,int fa){
	for(auto v:e[u])
	if(v!=fa) st.insert(val[v]);
	for(auto v:e[u])
	if(v!=fa){
		st.erase(st.find(val[v]));
		auto it=st.lower_bound(val[v]);
		int x=(it==st.end()?-1:(*it));
		if(it!=st.end()) f[v]=f[u]+1,st.erase(st.find(x));
		else f[v]=f[u];
		dfs(v,u);
		if(~x) st.insert(x); 
		st.insert(val[v]);
	}
	for(auto v:e[u])
	if(v!=fa) st.erase(st.find(val[v]));	
}
 
il void solve(){
	n=rd;
	for(re int i=1;i<=n;++i) val[i]=rd;
	for(re int i=1;i< n;++i){
		int u=rd,v=rd;
		e[u].push_back(v),
		e[v].push_back(u);
	}
	dfs(1,0);
	q=rd;
	while(q--) cout<<f[rd]<<"\n";
    return ;
}