Openjudge原題鏈接
POJ原題鏈接
題意
輸入樹(shù)的各邊及其長(zhǎng)度朵耕，求路徑小于等于k的點(diǎn)對(duì)數(shù)目題解
目標(biāo)：尋找長(zhǎng)度小于等于k的路徑
首先選取一個(gè)點(diǎn)作為根節(jié)點(diǎn)疤孕，那么路徑只有兩種情況：經(jīng)過(guò)根節(jié)點(diǎn)元莫；不經(jīng)過(guò)根節(jié)點(diǎn)
如果不經(jīng)過(guò)根節(jié)點(diǎn)卵凑，那么一定經(jīng)過(guò)最小公共子樹(shù)的根節(jié)點(diǎn)弄屡，劃歸為問(wèn)題1昼浦，可分治求解好唯。假定我們已經(jīng)有了根節(jié)點(diǎn)和樹(shù)的結(jié)構(gòu)竭沫，那么只需要進(jìn)行一次dfs，在dfs過(guò)程中求出每個(gè)節(jié)點(diǎn)到根節(jié)點(diǎn)的距離deep骑篙，以及計(jì)算出deep[x] + deep[y] <= k的pair數(shù)目蜕提，然后刪除根節(jié)點(diǎn)，然后進(jìn)入每一個(gè)子樹(shù)重新計(jì)算新的deep并計(jì)算數(shù)目靶端。但這樣會(huì)重復(fù)計(jì)算谎势。所以在第一次計(jì)算時(shí)應(yīng)當(dāng)減去屬于同一棵子樹(shù)的pair。
但是杨名，如果樹(shù)退化成一條鏈脏榆，那么時(shí)間復(fù)雜度為O(N ^ 2)。所以需要每次巧妙地選擇根節(jié)點(diǎn)使得最大的子樹(shù)最小台谍。即選擇重心, 這樣保證樹(shù)的高度不超過(guò)O(logN)须喂。
更多解釋參見(jiàn)代碼注釋
總的時(shí)間復(fù)雜度為O(N(logN)^2)
參考了ACMonster的解釋和wwwiskey的解題思路
參考了分治算法在樹(shù)的路徑問(wèn)題中的應(yīng)用——IOI2009中國(guó)國(guó)家集訓(xùn)隊(duì)論文
AC代碼如下
#if 0
要尋找長(zhǎng)度小于等于k的路徑
首先選取一個(gè)點(diǎn)作為根節(jié)點(diǎn)，那么路徑只有兩種情況：
1.經(jīng)過(guò)根節(jié)點(diǎn)
2.不經(jīng)過(guò)根節(jié)點(diǎn)
如果不經(jīng)過(guò)根節(jié)點(diǎn)趁蕊，那么一定經(jīng)過(guò)最小公共子樹(shù)的根節(jié)點(diǎn)坞生，劃歸為問(wèn)題1，可分治求解掷伙。
假定我們已經(jīng)有了根節(jié)點(diǎn)和樹(shù)的結(jié)構(gòu)是己，那么只需要進(jìn)行一次dfs，在dfs過(guò)程中求出每個(gè)節(jié)點(diǎn)到根節(jié)點(diǎn)的距離deep任柜，以及
計(jì)算出deep[x] + deep[y] <= k的pair數(shù)目赃泡，然后刪除根節(jié)點(diǎn)寒波，然后進(jìn)入每一個(gè)子樹(shù)重新計(jì)算新的deep并計(jì)算數(shù)目乘盼。但這
樣會(huì)重復(fù)計(jì)算升熊。所以在第一次計(jì)算時(shí)應(yīng)當(dāng)減去屬于同一棵子樹(shù)的pair。
但是绸栅，如果樹(shù)退化成一條鏈级野，那么時(shí)間復(fù)雜度為O(N ^ 2)。所以需要每次巧妙地選擇根節(jié)點(diǎn)使得最大的子樹(shù)最小粹胯。即選擇
重心, 這樣保證樹(shù)的高度不超過(guò)O(logN)蓖柔。
以下是選擇重心的源碼。
void getroot(int x, int fa)//x表示當(dāng)前結(jié)點(diǎn)风纠，fa表示x的父結(jié)點(diǎn)
{
son[x] = 1; F[x] = 0;//F數(shù)組記錄以x為根的最大子樹(shù)的大小
for (int i = Link[x]; i; i = e[i].next)
if (e[i].y != fa && !vis[e[i].y])//避免陷入死循環(huán)
{
getroot(e[i].y, x);//得到子結(jié)點(diǎn)信息
son[x] += son[e[i].y];//計(jì)算x結(jié)點(diǎn)大小
F[x] = max(F[x], son[e[i].y]);//更新F數(shù)組
}
F[x] = max(F[x], sum - son[x]);//sum表示當(dāng)前樹(shù)的大小况鸣，因?yàn)橐詘為根的情況還要考慮以x的父親為根的子樹(shù)大小。
if (F[x]<F[root])root = x;//更新當(dāng)前根
}
以下是刪除根節(jié)點(diǎn)后竹观，遞歸處理每一棵子樹(shù)（此時(shí)還不是子樹(shù)镐捧，是聯(lián)通塊，需要找新的根節(jié)點(diǎn)）的源碼
int solve(int x)
{
vis[x] = 1;//將當(dāng)前點(diǎn)標(biāo)記
for (int i = Link[x]; i; i = e[i].next)
if (!vis[e[i].y])
{
root = 0;//初始化根
sum = e[i].y;//初始化sum
getroot(x, 0);//找連通塊的根
solve(e[i].y);//遞歸處理下一個(gè)連通塊
}
}
int main()
{
build();//建樹(shù)
sum = f[0] = n;//初始化sum和f[0]
root = 0;//初始化root
getroot(1, 0);//找根
solve(root);//點(diǎn)分治
}
#endif
#include<iostream>
#include<algorithm>
#include<queue>
#include<vector>
#include<cstring>
#define MAXN 10005
using namespace std;
struct Edge {
int v, l;//v表示連接到的下一個(gè)節(jié)點(diǎn)臭增，l表示長(zhǎng)度
Edge(int v_, int l_) :v(v_), l(l_) {};
};
vector<Edge> g[MAXN];//用變長(zhǎng)數(shù)組存儲(chǔ)圖
vector<int> dep; //用來(lái)計(jì)算在某圖下懂酱，以某個(gè)節(jié)點(diǎn)作為根節(jié)點(diǎn)時(shí)的各子節(jié)點(diǎn)的deep，它不需要知道具體是哪個(gè)子節(jié)點(diǎn)
int dist[MAXN]; //
int n, k;
int vis[MAXN];
int f[MAXN];//存儲(chǔ)在當(dāng)前圖下,以某個(gè)節(jié)點(diǎn)作為根節(jié)點(diǎn)時(shí)誊抛，得到的最大子樹(shù)的大小
int root; //當(dāng)前找到的根節(jié)點(diǎn)
int ans; //最后要求的配對(duì)數(shù)目
int s[MAXN];//s for size列牺，記錄在當(dāng)前圖下每個(gè)節(jié)點(diǎn)的子樹(shù)大小之和，包括自己
int totalNodes;//n-刪除的點(diǎn)的個(gè)數(shù)
void getroot(int now, int fa) {
int u;
//s的存在是為了累加拗窃，然后得出父節(jié)點(diǎn)等所有祖先構(gòu)成子樹(shù)的大小
s[now] = 1;//自己
f[now] = 0;//存儲(chǔ)每個(gè)節(jié)點(diǎn)的最大子樹(shù)
for (int i = 0; i < g[now].size(); i++) {//不會(huì)陷入死循環(huán)的原因之一：樹(shù)上存在葉節(jié)點(diǎn)（只與父節(jié)點(diǎn)相連）
u = g[now][i].v;//子節(jié)點(diǎn)
if (u != fa && !vis[u]) {//不是父節(jié)點(diǎn)且未被切除瞎领，如果不排除父節(jié)點(diǎn)會(huì)陷入死循環(huán)
getroot(u, now);//遞歸地找到子樹(shù)的最大子樹(shù)和子樹(shù)的大小
s[now] += s[u]; //加入子樹(shù)的大小
f[now] = max(f[now], s[u]);//找最大子樹(shù)
}
}
f[now] = max(f[now], totalNodes - s[now]);//把父節(jié)點(diǎn)等所有祖先當(dāng)作一棵子樹(shù)
if (f[now] < f[root]) root = now;//找最大子樹(shù)最小的根節(jié)點(diǎn)
}
void getdep(int now, int fa) {//在某個(gè)圖某個(gè)根節(jié)點(diǎn)下求deep，天然的深度是dist[now]
int u;
dep.push_back(dist[now]);
s[now] = 1;
for (int i = 0; i < g[now].size(); i++) {
u = g[now][i].v;
if (u != fa && !vis[u]) {
dist[u] = dist[now] + g[now][i].l;
getdep(u, now);
s[now] += s[u];
}
}
}
int calc(int now, int len) {//在減去屬于同一棵子樹(shù)的時(shí)候,len是這個(gè)子樹(shù)到原根節(jié)點(diǎn)的距離
//我們把這個(gè)距離考慮進(jìn)來(lái)随夸，
dep.clear();
dist[now] = len;//以dist[now]作為基礎(chǔ)求deep
getdep(now, 0);//在當(dāng)前圖當(dāng)前根節(jié)點(diǎn)下九默，計(jì)算每個(gè)子節(jié)點(diǎn)的deep,放入dep數(shù)組
sort(dep.begin(), dep.end());
int cnt = 0;//統(tǒng)計(jì)數(shù)目
int l = 0, r = dep.size() - 1;
/*
用l表示左指針，r表示右指針逃魄，i從左向右遍歷荤西。
如果dep[i]+dep[j]≤k，則點(diǎn)對(duì)(i,t)(i<t≤j)都符合題意伍俘，將r-l加入答案中邪锌，并且l++；否則r--癌瘾。
*/
while (l < r) {
if (dep[l] + dep[r] <= k) {
cnt += r - l;
l++;
}
else r--;
}
return cnt;
}
void work(int now) {//以now作為根節(jié)點(diǎn)觅丰，在當(dāng)前的圖下計(jì)算滿(mǎn)足題意的pair個(gè)數(shù)
int u;
ans += calc(now, 0);//以now作為根節(jié)點(diǎn)，在當(dāng)前的圖下所有deep[i]+deep[j]<=k的(i,j)的數(shù)目
//然后減去屬于同一棵子樹(shù)的(i,j)妨退，于是得到了經(jīng)過(guò)根節(jié)點(diǎn)的所有(i,j)路徑
vis[now] = true;//剪掉根節(jié)點(diǎn)妇萄，得到不連通的幾棵子樹(shù)
for (int i = 0; i < g[now].size(); i++) {
u = g[now][i].v;
if (!vis[u]) {
ans -= calc(u, g[now][i].l);//減去屬于同一棵子樹(shù)的(i,j)
f[0] = totalNodes = s[u];//考慮連通的某棵子樹(shù)蜕企，其總的大小
root = 0;
getroot(u, 0);//找到新的根節(jié)點(diǎn)
work(root);//遞歸地增加不經(jīng)過(guò)當(dāng)前根節(jié)點(diǎn)，但是經(jīng)過(guò)新的根節(jié)點(diǎn)的路徑數(shù)目
}
}
}
int main() {
while (cin >> n >> k) {
if (!n && !k) break;
for (int i = 0; i <= n; i++)
g[i].clear();
memset(vis, 0, sizeof(vis));
int u, v, l;
for (int i = 1; i < n; i++) {//讀入n-1條邊
cin >> u >> v >> l;
g[u].push_back(Edge(v, l));
g[v].push_back(Edge(u, l));
}
f[0] = n;
root = 0;
totalNodes = n;
getroot(1, 0);
ans = 0;
work(root);
cout << ans << endl;
}
}
