Tree

Time Limit: 1000MS	Memory Limit: 30000K
Total Submissions: 21357	Accepted: 7006

Description

Give a tree with n vertices,each edge has a length(positive integer less than 1001).

Define dist(u,v)=The min distance between node u and v.

Give an integer k,for every pair (u,v) of vertices is called valid if and only if dist(u,v) not exceed k.

Write a program that will count how many pairs which are valid for a given tree.

Input

The input contains several test cases. The first line of each test case contains two integers n, k. (n<=10000) The following n-1 lines each contains three integers u,v,l, which means there is an edge between node u and v of length l.

The last test case is followed by two zeros.

Output

For each test case output the answer on a single line.

Sample Input

Sample Output

Source

LouTiancheng@POJ

題目連結：http://poj.org/problem?id=1741

題目大意：

給定一棵N個節點、邊上帶權的樹，再給出一個K，詢問有多少個數對(i,j)滿足i<j，且i與j兩點在樹上的距離小于等于K。

資料規模：

多組測試資料，每組資料滿足N≤10000，1≤邊上權值≤1000，1≤K≤10^9。

出處：

樓天城男人必做8題之一……

思路：

最容易想到的算法是：從每個點出發周遊整棵樹，統計數對個數。

由于時間複雜度O(N^2)，明顯是無法滿足要求的。

對于一棵有根樹，樹中滿足要求的一個數對所對應的一條路徑，必然是以下兩種情況之一：

1、經過根節點

2、不經過根節點，也就是說在根節點的一棵子樹中

對于情況2，可以遞歸求解，下面主要來考慮情況1。

設點i的深度為Depth[i]，父親為Parent[i]。

若i為根，則Belong[i]=-1，若Parent[i]為根，則Belong[i]=i，否則Belong[i]=Belong[Parent[i]]。

這三個量都可以通過一次BFS求得。

我們的目标是要統計：有多少對(i,j)滿足i<j，Depth[i]+Depth[j]<=K且Belong[i]<>Belong[j]

如果這樣考慮問題會變得比較麻煩，我們可以考慮換一種角度：

設X為滿足i<j且Depth[i]+Depth[j]<=K的數對(i,j)的個數

設Y為滿足i<j，Depth[i]+Depth[j]<=K且Belong[i]=Belong[j]數對(i,j)的個數

那麼我們要統計的量便等于X-Y

求X、Y的過程均可以轉化為以下問題：

已知A[1],A[2],...A[m]，求滿足i<j且A[i]+A[j]<=K的數對(i,j)的個數

對于這個問題，我們先将A從小到大排序。

設B[i]表示滿足A[i]+A[p]<=K的最大的p(若不存在則為0)。我們的任務便轉化為求出A所對應的B數組。那麼，若B[i]>i，那麼i對答案的貢獻為B[i]-i。

顯然，随着i的增大，B[i]的值是不會增大的。利用這個性質，我們可以線上性的時間内求出B數組，進而得到答案。

綜上，設遞歸最大層數為L，因為每一層的時間複雜度均為“瓶頸”——排序的時間複雜度O(NlogN)，是以總的時間複雜度為O(L*NlogN)

然而，如果遇到極端情況——這棵樹是一根鍊，那麼随意分割勢必會導緻層數達到O(N)級别，對于N=10000的資料是無法承受的。是以，我們在每一棵子樹中選擇“最優”的點分割。所謂“最優”，是指删除這個點後最大的子樹盡量小。這個點可以通過樹形DP在O(N)時間内求出，不會增加時間複雜度。這樣一來，即使是遇到一根鍊的情況時，L的值也僅僅是O(logN)的。

是以，改進後算法時間複雜度為O(Nlog^2N)，可以AC。

1 #include <iostream>
 2 #include <cstdio>
 3 #include <cmath>
 4 #include <cstring>
 5 #include <vector>
 6 #include <algorithm>
 7 using namespace std;
 8 const int N = 1e5+20, M = 1e2+10, mod = 1e9+7, inf = 1e9+1000;
 9 typedef long long ll;
10 
11 int n,m,root,t,ans,allnode,siz[N],K,head[N],vis[N],d[N];
12 int deep[N];//路徑長度//deep[0]子節點個數
13 int f[N];//重心
14 
15 struct edg{int to,next,v;}e[N * 4];//前向星存邊
16 void add(int u,int v,int w) {e[t].to=v;e[t].next=head[u];e[t].v=w;head[u]=t++;}//加邊
17 
18 //擷取重心
19 void getroot(int x,int fa) {
20     siz[x] = 1;
21     f[x] = 0;
22     for(int i=head[x];i;i=e[i].next) {
23         int to = e[i].to;
24         if(to == fa || vis[to]) continue;
25         getroot(to,x);
26         siz[x] += siz[to];
27         f[x] = max(f[x] , siz[to]);
28     }
29     f[x] = max(allnode-siz[x] , f[x]);
30     if(f[x] < f[root]) root = x;
31 }
32 
33 void getdeep(int x,int fa) {//擷取子樹所有節點與根的距離
34     deep[++deep[0]] = d[x];
35     for(int i=head[x];i;i=e[i].next) {
36         int to = e[i].to;
37         if(to == fa || vis[to]) continue;
38         d[to] = d[x] + e[i].v;
39         getdeep(to,x);
40     }
41 }
42 int cal(int x,int now) {//計算目前以重心x的子樹下，所有情況的答案
43     d[x]=now;deep[0]=0;
44     getdeep(x,0);
45     sort(deep+1,deep+deep[0]+1);
46     int all = 0;
47     for(int l=1,r=deep[0];l<r;) {
48         if(deep[l]+deep[r] <= K) {all += r-l;l++;}
49         else r--;
50     }
51     return all;
52 }
53 
54 void work(int x) {//以x為重心進行計算
55     vis[x] = 1;
56     ans+=cal(x,0);
57     for(int i=head[x];i;i=e[i].next) {
58         int to = e[i].to;
59         if(vis[to]) continue;
60         ans -= cal(to,e[i].v);
61         allnode = siz[to];
62         root=0;
63         getroot(to,x);
64         work(root);
65     }
66 }
67 
68 int main()
69 {
70     while(~scanf("%d%d",&n,&K)) {
71         if(!n&&!m) break;
72         memset(head,0,sizeof(head));
73         memset(vis,0,sizeof(vis));
74         t = 1;
75         for(int i=1;i<n;i++) {
76             int a,b,c;
77             scanf("%d%d%d",&a,&b,&c);
78             add(a,b,c) , add(b,a,c);
79         }
80         root=ans=0;
81         allnode=n;f[0]=inf;
82         getroot(1,0);
83         work(root);
84         printf("%d\n",ans);
85     }
86 }

作　　者：Angel_Kitty

出　　處：https://www.cnblogs.com/ECJTUACM-873284962/

關于作者：阿裡雲ACE，目前主要研究方向是Web安全漏洞以及反序列化。如有問題或建議，請多多賜教！

特此聲明：所有評論和私信都會在第一時間回複。也歡迎園子的大大們指正錯誤，共同進步。或者直接私信我

聲援部落客：如果您覺得文章對您有幫助，可以點選文章右下角【推薦】一下。您的鼓勵是作者堅持原創和持續寫作的最大動力！

歡迎大家關注我的微信公衆号IT老實人(IThonest)，如果您覺得文章對您有很大的幫助，您可以考慮賞部落客一杯咖啡以資鼓勵，您的肯定将是我最大的動力。thx.

我的公衆号是IT老實人(IThonest)，一個有故事的公衆号，歡迎大家來這裡讨論，共同進步，不斷學習才能不斷進步。掃下面的二維碼或者收藏下面的二維碼關注吧(長按下面的二維碼圖檔、并選擇識别圖中的二維碼)，個人QQ和微信的二維碼也已給出，掃描下面👇的二維碼一起來讨論吧！！！

歡迎大家關注我的Github，一些文章的備份和平常做的一些項目會存放在這裡。

POJ 1741 Tree(樹的點分治，入門題)

Tree