自动搬运

查看原文

来自洛谷，原作者为

	I_LOVE_XYN 这个家伙很菜，什么也没有留下

搬运于2025-08-24 23:06:51，当前版本为作者最后更新于2024-12-11 16:46:40，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

题目描述

在一个有 $N$ 节点的树内，以随机一个点为根的树共有几个权值比它小的子节点。

知识点提炼

记忆化搜索。

思路

我们发现这道题有 $10^5$ 的数据范围，首先想到的是 $O(n)$ 的时间复杂度，本蒟蒻考场上只能想到深搜，可是必须使用记忆化，保证所有节点只访问一次，减少冗余运算：

搜出所有比原点小的儿子，统计满足条件的儿子数量再将其回溯到父亲节点。如果访问过了该节点，直接将已经统计完的数据返回自己的父亲。

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
int n,a[1000006],vis[1000006];
vector<int> edge[1000006];
int dfs(int x){
	if(vis[x] != 0) return vis[x];
	//如果访问过了，直接返回之前的值，保证每个节点访问一次。 
	int cnt = 0;
	for(auto &v : edge[x])
		if(a[x] > a[v]) //如果连接的点比自己的小 
			cnt += dfs(v); //先统计 
	return vis[x] = cnt + 1;
	//这里的 1 是自己，因为自己属于节点，所以+1 
}
main(){
	cin >> n;
	for(int i = 1;i <= n; i++) cin >> a[i];
	for(int i = 1,x,y;i < n; i++){
		cin >> x >> y;
		edge[x].push_back(y);
		edge[y].push_back(x);
	}
	int ans = 0;
	for(int i = 1;i <= n; i++)
		ans = max(ans,dfs(i));
	//直接取最大值，不一定是节点1之类的 
	cout << ans;
} 

~蒟蒻的第一篇题解，求过求过求过~