程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> 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

 

 

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved