基環樹學習筆記

往一個樹上額外添加一條邊，稱得到的圖為基環樹。

基環樹點數和邊數相同，但是點數和邊數相同的圖不一定是基環樹。

另外，滿足以下性質的圖是基環森林（當聯通時是基環樹）：

每個點有且僅有一條出邊，這時候稱得到的圖為外向基環森林。
每個點有且僅有一條入邊，這時候稱得到的圖為內向基環森林。

對基環樹通常的處理方法有兩種。

第一種是任意斷開環上的一條邊，當作樹上問題做。最后再考慮這條邊對答案的影響。

第二種是斷開環上的所有邊，對得到的所有樹處理得到根的答案，轉化成環上的問題。

實現上，可以用 dfs 找出環，然后正常做。或者是在拓撲排序的過程中維護。

例題：

P4381 [IOI 2008] Island

求基環樹的直徑。

將環全部斷開，求出每個子樹內的最大值。dp 可以直接求出。

令 \(d_x\) 表示 \(x\) 子樹內的最深點的深度。

取環上任意一點 \(p\)，從 \(p\) 點處斷開得到鏈。令 \(s_x\) 表示 \(x\) 點在這條鏈上到 \(p\) 的距離。

那么經過環的最長距離就是

\[\max_{s_y>s_x} d_x+d_y+\max(s_y-s_x,s_x-s_y+\text{len}) \]

拆開可以直接線性維護。

code

#include <algorithm>
#include <iostream>
#include <vector>
#include <queue>

const int N = 1e6 + 7;
typedef long long i64;

namespace wyx {

int n, deg[N];
std::vector<std::pair<int, int>> g[N];
i64 dp[N], de[N], ans;

inline void pushup(int u) {
	dp[u] = 0;
	for(auto& [v, w]: g[u]) {
		if(deg[v] == 1) {
			dp[u] = std::max(dp[u], dp[v]);
			dp[u] = std::max(dp[u], de[u] + de[v] + w);
			de[u] = std::max(de[u], de[v] + w);
		}
	}
}

void toposort() {
	std::queue<int> q;
	for(int i = 1; i <= n; ++i) {
		if(deg[i] == 1) {
			q.push(i);
		}
	}
	while(!q.empty()) {
		int u = q.front(); q.pop();
		pushup(u);
		for(auto& [v, w]: g[u]) {
			if(--deg[v] == 1) q.push(v);
		}
	}
}

inline void solve(int x) {
	i64 res = 0;
	i64 a1 = -1e18, a2 = -1e18, b1 = -1e18, b2 = -1e18, pre = 0;
	int y = x;
	while(x) {
		deg[x] = 0;
		int nv = 0, nw = 0;
		for(auto& [v, w]: g[x]) {
			if(deg[v] == 2) {
				nv = v, nw = w; break;
			} 
		}

		pushup(x);
		res = std::max(res, dp[x]);

		b1 = std::max(b1, a1 + de[x] + pre);
		b2 = std::max(b2, a2 + de[x] - pre);
		a1 = std::max(a1, de[x] - pre);
		a2 = std::max(a2, de[x] + pre);

		if(!nv) {
			std::reverse(g[x].begin(), g[x].end());
			for(auto& [v, w]: g[x]) {
				if(v == y) { pre += w; break; }
			}
			break;
		}
		pre += nw, x = nv;
	}

	res = std::max(res, std::max(b1, b2 + pre));
	ans += res;
}

inline void main() {
	std::cin >> n;
	for(int i = 1; i <= n; ++i) {
		int x = i, y, z;
		std::cin >> y >> z;
		g[x].emplace_back(y, z);
		g[y].emplace_back(x, z);
		++deg[x], ++deg[y];
	}
	toposort();
	for(int i = 1; i <= n; ++i) {
		if(deg[i] == 2) {
			solve(i);
		}
	}
	std::cout << ans << "\n";	
}

};

int main() {
	std::ios::sync_with_stdio(0), std::cin.tie(0), std::cout.tie(0);
	wyx::main();
}

P2607 [ZJOI2008] 騎士

求基環樹上最大獨立集。

樹內用類似上一題的方法處理。

環上的部分，可以從任意邊 \(x \rightarrow y\) 斷開。

dp 時欽定 \(x\) 選/不選，dp 到 \(y\) 的狀態時合并答案。

code

#include <algorithm>
#include <iostream>
#include <queue>
#include <tuple>

namespace wyx {

const int N = 1e6 + 7;

typedef long long i64;
int n, deg[N]; i64 dp[N][2], w[N];
std::basic_string<int> g[N];

inline void pushup(int u) {
	dp[u][0] = 0, dp[u][1] = w[u];
	for(int& v: g[u]) {
		if(deg[v] == 1) {
			dp[u][0] += std::max(dp[v][0], dp[v][1]);
			dp[u][1] += dp[v][0];
		}
	}
}

inline void toposort() {
	std::queue<int> q;
	for(int i = 1; i <= n; ++i) {
		if(deg[i] == 1) q.push(i);
	}
	while(!q.empty()) {
		int u = q.front(); q.pop();
		pushup(u);
		for(int& v: g[u]) {
			if(--deg[v] == 1) q.push(v);
		}
	}
}

i64 ans = 0;
inline void solve(int x) {
	auto findnext = [](int x) { for(int& v: g[x]) if(deg[v] == 2) return v; return 0; };

	i64 dp[2][2];

	pushup(x);
	dp[1][1] = wyx::dp[x][1], dp[0][0] = wyx::dp[x][0];
	dp[1][0] = dp[0][1] = -1e18;	
	deg[x] = 0, x = findnext(x);

	while(x) {
		pushup(x);
		for(int k = 0; k < 2; ++k) {
			std::tie(dp[k][0], dp[k][1]) = std::make_pair(
				std::max(dp[k][0], dp[k][1]) + wyx::dp[x][0], 
				dp[k][0] + wyx::dp[x][1]
			);
		}

		deg[x] = 0, x = findnext(x);
	}		

	i64 res = std::max({dp[0][0], dp[0][1], dp[1][0]});
	ans += res;
}

inline void main() {
	std::cin >> n;
	for(int y, i = 1; i <= n; ++i) {
		std::cin >> w[i] >> y;
		g[i] += y, g[y] += i;
		++deg[i], ++deg[y];
	}
	toposort();
	for(int i = 1; i <= n; ++i) {
		if(deg[i] == 2) {
			solve(i);
		}
	}
	std::cout << ans << "\n";
}

};

int main() {
	std::ios::sync_with_stdio(0), std::cin.tie(0), std::cout.tie(0);
	wyx::main();
}

posted @ 2025-11-04 13:37 CuteNess 閱讀(6) 評論(0) 收藏舉報

刷新頁面返回頂部

CuteNess

基環樹學習筆記

基環樹學習筆記

P4381 [IOI 2008] Island

P2607 [ZJOI2008] 騎士

公告