题解：AT_abc246_g [ABC246G] Game on Tree 3

简单题。

按照结果的

A

从大到小顺序考虑。对于

A

的最大值，青木若想结果比它小，那么至少在到达写有该

A

的节点的父亲时，需要选择把它变成

0

。继续递推着，在处理完前面的限制后，发现当前

A

带来的限制可以表示为，在目前写有该

A

的节点的未被选用的祖先中，需选择一个，在到达它时，青木选择这个节点。否则可以逆推出高桥可以得到该

A

。当然，可以贪心地推得，最优时选的是深度最大的那一个。那么这样就可以使用并查集维护了，当找不到满足条件的祖先来选择时，答案自然就无法比它更小。

鲜花：出成联赛模拟 T2，

O(n\log n)

给 80 部分，把数据范围调成只放

O(n \alpha (n))

过，想来还是相当有杀伤力的。

CPP

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

inline int rd(){
	char c = getchar();
	while((c > '9' || c < '0') && c != '-') c = getchar();
	int ret = 0; 
	while(c >= '0' && c <= '9') ret = (ret << 3) + (ret << 1) + c - '0', c = getchar();
	return ret;
}

int n;
int father[200002];
vector<int> vec[200002];
void init(int pos,int faa){
	father[pos] = faa;
	for(int i=0;i<vec[pos].size();i++){
		if(vec[pos][i] == faa) continue;
		init(vec[pos][i], pos);
	}
}
pair<int,int> Data[200002];
int fa[200002], cnt[200002], node[2000002];
int getfa(int u){
	if(fa[u] == u) return u;
	fa[u] = getfa(fa[u]);
	return fa[u];
}

int main(){
	
	n = rd();
	for(register int i=1;i<=n;i++) fa[i] = i, cnt[i] = 1, node[i] = i;
	for(register int i=1;i<=n-1;i++){
		scanf("%d",&Data[i].first);
		Data[i].second = i + 1;
	}
	for(int i=1;i<n;i++){
		int u, v;
		scanf("%d%d",&u,&v);
		vec[u].push_back(v);
		vec[v].push_back(u);
	}
	sort(Data+1,Data+n);
	init(1, 0); 
	
	register int i;
	
	for(i=n-1;i>=1;i--){
		int u = getfa(father[Data[i].second]);
		if(node[u] == 0) break;
		if(node[u] == 1) {
			node[u] = 0;
			continue;
		}
		int v = getfa(father[node[u]]);
		int then = node[v];
		if(cnt[u] > cnt[v]) swap(u, v);
		cnt[v] += cnt[u], fa[u] = v;
		node[v] = then;
	}
	printf("%d",Data[i].first);
	
	return 0;
}

题解：AT_abc246_g [ABC246G] Game on Tree 3

文章操作

相关推荐

评论

题解：AT_abc246_g [ABC246G] Game on Tree 3