. 电

一道不错的记忆化搜索题目！

在建图上需要动一点点小手脚，也是很简单的思维题！

AcWing 4742. 电 原题链接

最大连通分量：+ 记忆化搜索

本题卡了，，可以关闭流同步或者改成，

本题其实很简单（），是求最大连通分量的板子题

建图

只需要在建图的时候，保留从电容大的节点流向电容小的节点的边（这里需要仔细理解喔！），其余边都不需要保留，接下来就是求最大连通分量啦！

动态规划

状态定义：表示以第个节点为根的最大连通分量大小。
状态转移方程：（其中为的子节点）

在这里，有可能重复计算了某个节点的分量数，因此我们使用记忆化搜索剪枝。

搜索代码

int dfs(int u) {
	if (dp[u]) return dp[u];

	dp[u] = 1;
	for (int i = h[u]; ~i; i = ne[i]) {
		int j = e[i];
		dp[u] += dfs(j);
	}

	return dp[u];
}

时间复杂度

完整代码

码风比较差，请见谅

#include<ios>
#include<iomanip>
#include<iostream>
#include<cstdio>
#include<fstream>
#include<algorithm>
#include<deque>
#include<vector>
#include<list>
#include<forward_list>
#include<string>
#include<cstring>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<unordered_map>
#include<unordered_set>
#include<algorithm>
#include<functional>
#include<cstdlib>
#include<cmath>

using namespace std;

typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;

#define int long long
#define endl '\n'
#define IOS ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
#define _rep(i, a, b) for (int i = (a); i <= (b); ++i)
#define _per(i, a, b) for (int i = (b); i >= (a); --i)
#define debug(a) cout << #a << " = " << a << endl
#define PI acos(-1)
#define lowbit(x) (x&-x)

const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const double EPS = 1e-8;

const int dx[4] = { -1, 0, 1, 0 };
const int dy[4] = { 0, -1, 0, 1 };

int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
int lcm(int a, int b) { return a * b / gcd(a, b); }

inline int read() {
	int x = 0, w = 1;
	char ch = getchar();
	while (ch < '0' || ch > '9') { if (ch == '-') w = -1, ch = getchar(); }
	while (ch >= '0' && ch <= '9') { x = x * 10 + (ch - '0'), ch = getchar(); }
	return x * w;
}

inline void write(int x) {
	static int sta[35];
	int top = 0;
	do {
		sta[top++] = x % 10, x /= 10;
	} while (x);
	while (top) putchar(sta[--top] + 48);  // 48 是 '0'
}


const int N = 2e5 + 10;

int T, n, c[N], dp[N], cases;
int h[N], e[N], ne[N], idx;
int son[N];

void add(int a, int b) {
	e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

int dfs(int u) {
	if (dp[u]) return dp[u];

	dp[u] = 1;
	for (int i = h[u]; ~i; i = ne[i]) {
		int j = e[i];
		dp[u] += dfs(j);
	}

	return dp[u];
}

void solve(void) {

	cin >> n;

	idx = 0;
	memset(h, -1, sizeof h);
	memset(dp, 0, sizeof dp);
	memset(son, 0, sizeof son);

	for (int i = 1; i <= n; i++) {
		cin >> c[i];
	}

	for (int i = 1; i < n; i++) {
		int u, v;
		cin >> u >> v;
		if (c[u] > c[v]) {
			add(u, v);
			son[v] = 1;
		}
		else if (c[u] < c[v]) {
			add(v, u);
			son[u] = 1;
		}
	}

	int ans = 0;
	for (int i = 1; i <= n; i++) {
		if (!son[i]) {
			ans = max(ans, dfs(i));
		}
	}
	cout << "Case #" << ++cases << ": ";
	cout << ans << endl;

}

signed main(void) {

	IOS;
	T = 1;
	// T = read();
	cin >> T;
	while (T--) {
		solve();
	}

	return 0;
}