難度 尚未評(píng)定
Description
給定一顆有個(gè)節(jié)點(diǎn)的樹(shù)，每條邊有一個(gè)權(quán)值。樹(shù)上兩個(gè)節(jié)點(diǎn)
和
之間的路徑長(zhǎng)度就是路徑上各條邊的權(quán)值的合。
求樹(shù)上長(zhǎng)度不超過(guò)的路徑有多少條。
CCYOS
這是一道點(diǎn)分治例題挤庇。
- 若指定
節(jié)點(diǎn)為根，則對(duì)于節(jié)點(diǎn)
a. 經(jīng)過(guò)根結(jié)點(diǎn)
b. 包含于- 對(duì)于第二類路徑淘菩，可以視作每顆子樹(shù)下的子問(wèn)題遞歸處理。
對(duì)于第一類路徑屠升，至多由兩段組成：
和
潮改。求解第一類路徑時(shí)，要記錄
數(shù)組和
數(shù)組腹暖，分別表示根結(jié)點(diǎn)到該點(diǎn)的距離和該點(diǎn)屬于哪一棵子樹(shù)汇在。根據(jù)題意，
![\begin{cases} { rt[x] \not= rt[y]}\\ \ d[x] + d[y] \leq K \end{cases}](https://math.jianshu.com/math?formula=%5Cbegin%7Bcases%7D%20%7B%20rt%5Bx%5D%20%5Cnot%3D%20rt%5By%5D%7D%5C%5C%20%5C%20d%5Bx%5D%20%2B%20d%5By%5D%20%5Cleq%20K%20%5Cend%7Bcases%7D)
- 構(gòu)建
函數(shù)脏答，統(tǒng)計(jì)在以p為根的樹(shù)中滿足上述要求的點(diǎn)對(duì)個(gè)數(shù)糕殉。
- 實(shí)現(xiàn)方法：
一 · 樹(shù)上直接統(tǒng)計(jì)
對(duì)于根結(jié)點(diǎn)p下的子樹(shù)為。
對(duì)于中的每個(gè)節(jié)點(diǎn)
殖告，將在子樹(shù)
中滿足
的節(jié)點(diǎn)
數(shù)量加入答案中即可阿蝶。
可建立樹(shù)狀數(shù)組求解。
本做法應(yīng)用：YALI 0J 2902B 文學(xué)
二·指針掃描數(shù)組
把樹(shù)上每個(gè)點(diǎn)放入數(shù)組黄绩，并將數(shù)組按照
使用兩個(gè)指針從前后掃描數(shù)組
不難發(fā)現(xiàn)在向右掃描的過(guò)程中爽丹，
的范圍是從右往左單調(diào)遞減的筑煮。（不能加大數(shù)了）
另外處理一個(gè)數(shù)組，維護(hù)在
之間滿足
的位置
的個(gè)數(shù)粤蝎。
則易得當(dāng)時(shí)真仲，答案即為
。
本做法應(yīng)用：POJ 1741 Tree- 總結(jié)點(diǎn)分治算法過(guò)程：
a.找到樹(shù)的中心p作為根結(jié)點(diǎn)初澎。
b.從p進(jìn)行dfs秸应，求出rt和d數(shù)組。
c.clac(p)統(tǒng)計(jì)答案。
d.刪除根結(jié)點(diǎn)p灸眼，對(duì)p的每顆子樹(shù)進(jìn)行a - d。
code
#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
struct EDGE{ int to,next; long long w; }edg[80005];
int n,tot,root,limit,siz,vis[40005],head[40005],size[40005];
long long k,ans,l,r;
long que[40005],dis[40004];
inline void adde(int x,int y,int w){ edg[++tot].to = y; edg[tot].w = w; edg[tot].next = head[x]; head[x] = tot; }
inline void getroot(int p,int fa){
size[p] = 1; int num = 0;//從p點(diǎn)出發(fā)的子樹(shù)大小
for(int i = head[p];i;i = edg[i].next){
int to = edg[i].to;
if(fa == to||vis[to])continue;
getroot(to,p); size[p] += size[to];
num = max(num,size[to]);
}
num = max(num,siz - size[p]);
if(num < limit){//limit:當(dāng)前最小
limit = num; root = p;
}
}
inline void getdis(int p,int fa){
que[++r] = dis[p];
for(int i = head[p];i;i = edg[i].next){
int to = edg[i].to;
if(to == fa||vis[to])continue;
dis[to] = dis[p] + edg[i].w; getdis(to,p);
}
}
inline long long clac(int p,int v){
r = 0; dis[p] = v;
long long sum = 0;
getdis(p,0);
l = 1;
sort(que + 1,que + r + 1);
while(l < r){
if(que[l] + que[r] <= k)sum += r - l,++l;
else r--;
}
return sum;
}
inline void dfs(int p){
ans += clac(p,0); vis[p] = 1;//將p點(diǎn)作為根結(jié)點(diǎn)是否處理完畢
for(int i = head[p];i;i = edg[i].next){
int to = edg[i].to;
if(vis[to])continue;
ans -= clac(to,edg[i].w);
siz = size[to];
limit = 2147483647;
getroot(to,0);
dfs(root);
}
}
inline void init(){
tot = 0;ans = 0;
for(int i = 1;i <= n;++i)head[i] = 0,vis[i] = 0;
}
int main(){
scanf("%d%lld",&n,&k);
int x,y; long long w;
while(n&&k){ for(int i = 1;i < n;++i){
scanf("%d%d%lld",&x,&y,&w);
adde(x,y,w); adde(y,x,w);
}
limit = 2147483647;//
siz = n;//對(duì)于第一棵子樹(shù)的大小限制
getroot(1,0);//找到樹(shù)的重心墓懂，更新root
dfs(root);//從root開(kāi)始遞歸統(tǒng)計(jì)更新答案
printf("%lld\n",ans); init();
scanf("%d%lld",&n,&k);
}
return 0;
}
