程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> POJ 1741 Tree（樹分治|ltc男人八題）

POJ 1741 Tree（樹分治|ltc男人八題）

編輯：關於C++

題意：求樹上距離小於等於K的點對有多少個。

思路：這道題很容易想到樹分治，對於當前的根節點來說，任意兩個結點之間要麼過根結點，要麼在一棵子樹中。

那麼我們dfs一次求出所有點到根結點的距離，然後用o(n)的時間判定有多少節點對符合，（判斷方法稍後說）

但是這樣有很多在一顆子樹中的節點對我們會求重復，我們需要減去在一棵子樹中結點對小於等於k的數量，也就是說，我們這一步求的是在不同子樹中距離小於等於k的節點對的個數。

接下來說判定方法，將每個點到根結點的距離排序，用兩個指針指向隊首和隊尾，當結點距離和大於k時，隊尾指針減一

否則更新答案並將隊首指針加一。

這道題還有一個問題樣例相當好，因為假如樹退化成一條鏈時，如果我們以任意結點為根那麼遞歸深度將達到O(n)，將會tle

所以每次樹分治時我們都要找到當前樹的重心，並以重心為根繼續分治。

#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include 
#include
#include 
#include
#define eps 1e-6 
#define LL long long  
#define pii (pair)
//#pragma comment(linker, /STACK:1024000000,1024000000) 
using namespace std;  

const int maxn = 10000 + 100;
const int INF = 0x3f3f3f3f;

int n, root, k, cnt; //root記錄重心 
int des[maxn], bal[maxn], vis[maxn];//des記錄以該節點為祖先的後代數，bal記錄以該節點為根的最大子樹的節點數 
vector G[maxn], L[maxn], dist; 

void get_root(int cur, int fa) {
	des[cur] = 1;
	bal[cur] = 0;
	int sz = G[cur].size();
	for(int i = 0; i < sz; i++) {
		int u = G[cur][i];
		if(vis[u] || u == fa) continue;
		get_root(u, cur);
		des[cur] += des[u];
		bal[cur] = max(bal[cur], des[u]);
	}
	bal[cur] = max(bal[cur], cnt-des[cur]);
	if(bal[cur] < bal[root]) root = cur;
} 

void dfs(int cur, int init, int fa) {
	cnt++;
	dist.push_back(init);
	int sz = G[cur].size(); 
	for(int i = 0; i < sz; i++) {
		int u = G[cur][i];
		if(vis[u] || u==fa) continue;
		dfs(u, init+L[cur][i], cur);
	}
}

int cal(int cur, int init) {
	int ans = 0;
	dist.clear();
	dfs(cur, init, -1);
	sort(dist.begin(), dist.end());
	int l = 0, r = dist.size()-1;
	while(l