专栏文章

P11378 题解

FFlambler
P11378题解参与者 3已保存评论 3

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
3 条
当前快照
1 份
快照标识符
@miquu9j6
此快照首次捕获于
2025/12/04 11:06
3 个月前
此快照最后确认于
2025/12/04 11:06
3 个月前
查看原文

P11378 题解

Step 0 Preface 前言

博客食用更佳 本蒟蒻的第 1 篇题解。场上 30 min秒掉，也是我唯一做出来的一道题，当时交了三次，前两次都得了 2.5 分，第三次我不抱太大信心，但是看着那一抹绿色，我陷入了沉思……另一道题只得了 7.5 分，估完分后发现总分 66.5 ，能过，但不能免普及初赛。

Step 1 Problem+Idea 题意+思路

简单来说求这棵树满足 ai<aja_i<a_j 的最大连通分量。

Step 2 Code 代码

用 bfs 只能得 40 分，赛时 bfs 竟然过了，不得不说数据太水了，这是 bfs 的代码:
CPP
#include<bits/stdc++.h>
#define llmax numeric_limits<long long>::max()
#define llmin numeric_limits<long long>::min()
#define imax numeric_limits<int>::max()
#define imin numeric_limits<int>::min()
#define pb push_back
#define gc getchar
#define pc putchar
#define ps puts
#define nl ps("")
#define chkup(ch) ch>='A'&&ch<='Z'
#define chklow(ch) ch>='a'&&ch<='z'             //请忽略我的火车头 
using namespace std;
const int N=1e5+10;
int a[N], ans;
vector<int> g[N];
bool vis[N];
bool chk(int x, int s) {              //x 代表当前遍历到的这个点，s 代表它的上一个点。 
	return !vis[x]&&a[x]<a[s];        //检查是否能入队。 
}
void bfs(int s) {
	int cnt=0;                                   //用来统计连通块大小 
	queue<int> q;
	q.push(s);
	vis[s]=true;
	while(!q.empty()) {
		int x=q.front();                       //1.获取队首元素 
		q.pop();                                 //2.出队
		cnt++;                                   //找到一个点就让连通块大小加1 
		for(int i = 0;i<g[x].size();i++) {       //3.模拟扩展 
			if(chk(g[x][i], x)) {
				q.push(g[x][i]);
				vis[g[x][i]]=true;
			}
		}
	}
	ans=max(ans, cnt);    //将连通块大小与答案相比较
}
int main() {
	int n;
	scanf("%d", &n);
	for(int i = 1;i<=n;i++) {
		scanf("%d", a+i);
	}
	for(int i = 1;i<n;i++) {
		int u, v;
		scanf("%d%d", &u, &v);
		g[u].pb(v);                       //建边 
		g[v].pb(u);
	}
	for(int i = 1;i<=n;i++) {
		for(int j = 1;j<=n;j++) {
			vis[j]=false;
		}
		bfs(i);                       //所有点开始bfs
	}
	printf("%d", ans);                    //输出答案
	return 0;
}
40 pts record
那么开始思考正解，用 bfs 可能效率不会太高，可以用 2 个 dfs 来解答:
首先第 1 个 dfs 用来求从每个节点开始的满足 ai<aja_i<a_j 的数量:
CPP
void dfs1(int x, int f) {
	tmp[x]=1;                                   //将初始值设为1 
	for(int i = 0;i<a[x].size();i++) {
		if(a[x][i]!=f) {                        //如果这个节点不是父节点，防止自环 
			dfs1(a[x][i], x);                   //遍历下一个节点 
			if(w[a[x][i]]<w[x]) {
				tmp[x]+=tmp[a[x][i]];           //如果满足条件，则把子树的数量加给这个点的数量 
			}
		}
	}
}
然后第 2 个 dfs 用来求答案:
CPP
void dfs2(int x, int f) {
	if(w[x]>w[f]) {                             //如果满足就将父节点的大小和答案增加给当前节点的答案，因为从当前节点开始会比从父节点开始会多 
		ans[x]+=ans[f]+tmp[f];
	}
	for(int i = 0;i<a[x].size();i++) {
		if(a[x][i]!=f) {                        //如果这个节点不是父节点，防止自环
			dfs2(a[x][i], x);                   //遍历下一个节点
		}
	}
}
每个 dfs 可以从任意节点开始。
完整代码:
CPP
#include<bits/stdc++.h>
#define llmax numeric_limits<long long>::max()
#define llmin numeric_limits<long long>::min()
#define imax numeric_limits<int>::max()
#define imin numeric_limits<int>::min()
#define pb push_back
#define gc getchar
#define pc putchar
#define ps puts
#define nl ps("")
#define chkup(ch) ch>='A'&&ch<='Z'
#define chklow(ch) ch>='a'&&ch<='z'             //请忽略我的火车头 
using namespace std;
const int N=1e5+10;
int w[N], tmp[N], ans[N], out;
vector<int> a[N];
void dfs1(int x, int f) {
	tmp[x]=1;                                   //将初始值设为1 
	for(int i = 0;i<a[x].size();i++) {
		if(a[x][i]!=f) {                        //如果这个节点不是父节点，防止自环 
			dfs1(a[x][i], x);                   //遍历下一个节点 
			if(w[a[x][i]]<w[x]) {
				tmp[x]+=tmp[a[x][i]];           //如果满足条件，则把子树的数量加给这个点的数量 
			}
		}
	}
}
void dfs2(int x, int f) {
	if(w[x]>w[f]) {                             //如果满足就将父节点的大小和答案增加给当前节点的答案，因为从当前节点开始会比从父节点开始会多 
		ans[x]+=ans[f]+tmp[f];
	}
	for(int i = 0;i<a[x].size();i++) {
		if(a[x][i]!=f) {                        //如果这个节点不是父节点，防止自环
			dfs2(a[x][i], x);                   //遍历下一个节点
		}
	}
}
int main() {
	int n;
	scanf("%d", &n);
	for(int i = 1;i<=n;i++) {
		scanf("%d", w+i);
	}
	for(int i = 1;i<n;i++) {
		int u, v;
		scanf("%d%d", &u, &v);
		a[u].pb(v);                 //建边 
		a[v].pb(u);
	}
	dfs1(1, 0);                     //从1开始，1的父节点是0 
	dfs2(1, 0);
	for(int i = 1;i<=n;i++) {
		ans[i]+=tmp[i];             //最终答案为大小和答案相加的和 
	}
	for(int i = 1;i<=n;i++) {
		out=max(out, ans[i]);       //比大小 
	}
	printf("%d", out);
	return 0;
}
100 pts record

评论

共 3 条评论，欢迎与作者交流。

正在加载评论...