本文正體字版由OpenCC轉換
問題簡述
給定一棵邊上帶權的樹,求一個平均價值最大的簡單路徑。路徑的平均價值定義爲路徑的帶權長度與不帶權長度的比值。
問題分析
在一棵樹上直接找這樣的路徑是很困難的,因此我們考慮將問題分解。一個基本的想法是在樹上分治,爲保證對數級別的時間複雜度,必須使用基於點的剖分[1]。每次找到樹的重心[2]作爲根節點,然後將根節點的子樹平均分爲兩部分,兩部分共用根節點。對每一部遞歸求解,然後把這兩部分合並。求樹的重心的方法是隨便找一個根,求出每個子樹的大小,找到max{i.child.size,N-i.size}最小的i,i就是樹的重心。重心可能有多個,找一個即可。
對於一個分治的局面,每一部分都是當前根節點的一些子樹組成的森林,再加上根節點,所以每一部分仍然是一棵樹。最優的路徑可能在某一個分治的部分中,也可能跨過根節點在兩個部分中。前者可以直接遞歸下去求解,重點是處理後者的情況。這時需要做的一個重要轉化是二分答案,由於答案的範圍是已知的,我們可以在答案的範圍內二分答案的值A,然後把樹上每一條邊的權值都減去A。判斷有解的方法也就變成了判斷是否存在一條帶權長度大於等於0的路徑,繼續轉化就是,判斷最長的帶權路徑的帶權長度是否大於等於0。
如何找出跨兩部分的最長帶權路徑呢?由於路徑的長度必須滿足在[L,U]之間,簡單的想法是在一個部分中枚舉路徑的一個端點的深度i,那麼這條路徑的另一端在另一個部分中的深度一定是在[L-i,U-i]之間。爲保證路徑最長,第一個部分中深度爲i的一段顯然應該是這個部分中深度爲i的所有路徑中帶權長度最大的那一條,第二部分也同理,不過要枚舉深度在[L-i,U-i]的最大值。如果我們確定i的枚舉順序以後,[L-i,U-i]區間的移動就是單調的,因此可以用單調隊列維護最大值,因此時間複雜度就是線性的。
算法描述
-
求出當前樹的重心,對當前樹進行點剖分。
-
二分當前樹中平均長度最大值A,判斷二分範圍是否滿足精度,如果滿足轉到步驟5,否則轉到步驟3。
-
將樹上所有邊權值減去A,求出剖分的兩部分每個深度上的最長帶權路徑長度。
-
用單調隊列維護,求出跨兩部分的帶權路徑長度最大值,判斷該值是否大於等於0,轉到步驟2。
-
對剖分的兩部分分別遞歸求解,如果這一部分大小大於等於L的話。
複雜度分析
對樹點剖分的時間複雜度爲O(logN),求重心的時間複雜度爲O(N),二分答案時間複雜度爲O(logV),求帶權路徑長度最大值時間複雜度爲O(N),因此總時間複雜度爲O(NlogNlogV)。
參考程序
/*
* Problem: NOI Winter Camp 2010 Rebuild
* Author: Guo Jiabao
* Time: 2010.3.12 14:01
* Label: Solved
* Memo: Binary Search + Monoqueue + Devide & Conquer on tree
*/
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <iostream>
#include <sstream>
#include <vector>
#include <list>
#include <deque>
#include <string>
#include <queue>
using namespace std;
#define var(a,b) typeof(b) a(b)
#define foreach(a,b) for (var(a,b.begin());a!=b.end();++a)
const int MAXN = 100001,MAXM=MAXN*2,INF=~0U>>1;
const double LIM=1e6,FINF = 1e20;
struct Monoqueue
{
struct element
{
int key;
double value;
}Q[MAXN];
int head,rear;
void reset()
{
rear = 0;
head = 1;
}
void insert(int k,double v)
{
while (rear >= head && v > Q[rear].value)
rear--;
Q[++rear].value = v;
Q[rear].key = k;
}
int getmax(int L)
{
while (Q[head].key < L)
head++;
return Q[head].key;
}
}MQ;
struct edge
{
edge *next;
int t,c;
};
int N,L,U,EC,timestamp,Total;
int t_ctd,t_ctd_csm,md1,md2,*t_maxdpt;
int size[MAXN],depth[MAXN];
double length[MAXN],d1m[MAXN],d2m[MAXN],*t_dm;
edge *V[MAXN],ES[MAXM];
int ava[MAXN];
double Ans,t_delta;
inline void addedge(int a,int b,int c)
{
edge *e=ES+ ++EC;
e->next = V[a];
e->t = b;
e->c = c;
V[a] = e;
}
void init()
{
freopen("rebuild.in","r",stdin);
freopen("rebuild.out","w",stdout);
scanf("%d%d%d",&N,&L,&U);
for (int i=1;i<N;i++)
{
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
addedge(a,b,c);
addedge(b,a,c);
if (L == 1 && c > Ans)
Ans = c;
}
}
void get_depth(int i)
{
for (edge *e=V[i];e;e=e->next)
{
int j = e->t;
if (ava[j] != 0) continue;
if (depth[j] == -1)
{
depth[j] = depth[i] + 1;
get_depth(j);
}
}
}
int get_longest_line(int start)
{
int i,maxdepth;
memset(depth,-1,sizeof(depth));
depth[start] = maxdepth = 0;
get_depth(start);
for (i=1;i<=N;i++)
if (ava[i] == 0 && depth[i] > maxdepth)
{
maxdepth = depth[i];
start = i;
}
memset(depth,-1,sizeof(depth));
depth[start] = maxdepth = 0;
get_depth(start);
for (i=1;i<=N;i++)
if (ava[i] == 0 && depth[i] > maxdepth)
maxdepth = depth[i];
return maxdepth;
}
void get_size(int i)
{
int csm = 0;
size[i] = 1;
for (edge *e=V[i];e;e=e->next)
{
int j = e->t;
if (ava[j] != 0) continue;
if (size[j] == -1)
{
get_size(j);
size[i] += size[j];
if (size[j] > csm)
csm = size[j];
}
}
if (Total - size[i] > csm)
csm = Total - size[i];
if (csm < t_ctd_csm)
{
t_ctd_csm = csm;
t_ctd = i;
}
}
int get_centroid(int i)
{
memset(size,-1,sizeof(size));
t_ctd_csm = INF;
get_size(i);
memset(size,-1,sizeof(size));
return t_ctd;
}
void count_size(int i)
{
size[i] = 1;
for (edge *e=V[i];e;e=e->next)
{
int j = e->t;
if (ava[j] != 0) continue;
if (size[j] == -1)
{
count_size(j);
size[i] += size[j];
}
}
}
void count_depth_max_length(int i)
{
//求最大深度
if (depth[i] > *t_maxdpt)
*t_maxdpt = depth[i];
for (edge *e=V[i];e;e=e->next)
{
int j = e->t;
if (ava[j] != 0) continue;
//求該深度最大帶權長度
if (length[i] > t_dm[depth[i]])
t_dm[depth[i]] = length[i];
if (depth[j] == -1)
{
length[j] = length[i] + e->c - t_delta;
depth[j] = depth[i] + 1;
count_depth_max_length(j);
}
}
}
bool check(double delta,int ctd,edge *f)
{
edge *e;
int i,j,k;
for (i=0;i<=N;i++)
d1m[i] = d2m[i] = -FINF;
t_delta = delta;
memset(depth,-1,sizeof(depth));
memset(length,-1,sizeof(length));
md1 = md2 = 0;
length[ctd] = depth[ctd] = 0;
//統計部份1
t_dm = d1m;
t_maxdpt = &md1;
for (e=V[ctd];e != f;e=e->next)
{
int j=e->t;
if (ava[j] !=0) continue;
length[j] = e->c - t_delta;
depth[j] = 1;
count_depth_max_length(j);
}
//統計部份2
t_dm = d2m;
t_maxdpt = &md2;
for (e=f;e;e=e->next)
{
int j=e->t;
if (ava[j] !=0) continue;
length[j] = e->c - t_delta;
depth[j] = 1;
count_depth_max_length(j);
}
//單調隊列維護最大值
//確定左邊界
i = U-1;
if (i > md1)
i = md1;
//確定右邊界
k = L-i;
if (k < 1)
k = 1;
MQ.reset();
for (j=k;j<U-i && j<=md2 ;j++)
MQ.insert(j,d2m[j]);
double curv,maxv=-INF;
for (;i>0 && L-i<=md2;i--)
{
j = U-i;
if (j<=md2)
MQ.insert(j,d2m[j]);
int k = MQ.getmax(L-i);
curv = d1m[i] + d2m[k];
if (curv > maxv)
maxv = curv;
}
return maxv >= 0;
}
double binary(int ctd,edge *f)
{
double a=0,b=LIM,m;
while (b - a >= 0.0001)
{
m = (a+b)/2;
if (check(m,ctd,f))
a = m;
else
b = m;
}
return a;
}
void dct(int start)
{
int nowt = ++timestamp;
int line = get_longest_line(start);
if (line<=L || line<=2)
return;
int ctd = get_centroid(start); //取得重心
double cur;
//分割兩部份
count_size(ctd);
int pls = 0,pls2 = 0;
edge *e,*f;
for (e=V[ctd];e;e=e->next)
{
int j=e->t;
if (ava[j] !=0) continue;
pls += size[j];
if (pls + pls + 1 >= size[ctd] - 1)
{
f = e->next;
pls2 = size[ctd] - pls;
pls++;
break;
}
}
//合併兩部份
cur = binary(ctd,f);
if (cur > Ans)
Ans = cur;
//遞歸部份1
int j;
if (pls-1 >= L)
{
for (e=f;e;e=e->next)
if (ava[j=e->t] ==0)
ava[j] = nowt;
Total = pls;
dct(ctd);
for (edge *e=f;e;e=e->next)
if (ava[j=e->t] ==nowt)
ava[j] = 0;
}
//遞歸部份2
if (pls2-1 >= L)
{
for (e=V[ctd];e!=f;e=e->next)
if (ava[j=e->t] ==0)
ava[j] = nowt;
Total = pls2;
dct(ctd);
for (e=V[ctd];e!=f;e=e->next)
if (ava[j=e->t] ==nowt)
ava[j] = 0;
}
}
void solve()
{
memset(ava,0,sizeof(ava));
Total = N;
dct(1);
}
int main()
{
init();
solve();
printf("%.3lf\n",Ans);
return 0;
}
</>[1] 具體證明參見2009年集訓隊論文《分治算法在樹的路徑問題中的應用》。
[2] 樹的重心就是滿足“刪除該點後,剩餘的最大的子樹頂點數最少”的點。
上次修改時間 2017-05-22