題目描述：
給你一個(gè)N(N<10000)個(gè)點(diǎn)的有權(quán)樹(shù)，請(qǐng)問(wèn)距離不超過(guò)K(K<1,000,000,000)的點(diǎn)對(duì)有多少個(gè)?
吐槽：
1. 大家想不想看男人八題的總結(jié)？ 有需求的話(huà)我就一天寫(xiě)一篇~~~~ (之前切了3道...不過(guò)寫(xiě)的很挫)
2. 代碼寫(xiě)的很挫，加上各種注釋/調(diào)試語(yǔ)句干了2.5k...
3. 說(shuō)好的今天學(xué)塊鏈呢...
算法分析：
又是一道計(jì)數(shù)問(wèn)題，總的想法是分治然后容斥...
對(duì)于一個(gè)有根樹(shù)，計(jì)算路徑經(jīng)過(guò)root的點(diǎn)對(duì)的個(gè)數(shù)。如果被計(jì)算出來(lái)了，再去計(jì)算它的子樹(shù)。
問(wèn)題是如何保證它的子樹(shù)分布的比較“均勻”呢？ 有個(gè)定理：
存在一個(gè)點(diǎn)使得分出的子樹(shù)的結(jié)點(diǎn)個(gè)數(shù)均不大于 N / 2 (證明略)
我們的目的就是找到一個(gè)這樣的點(diǎn)，即樹(shù)的重心(可能有多個(gè))。
做法就是從任意一點(diǎn)開(kāi)始做樹(shù)形DP，對(duì)于某個(gè)點(diǎn)u判斷每個(gè)子樹(shù)的sum值和SUM-sum[u]的值是否全部不大于n/2...
分(divide)的問(wèn)題解決了，那么如果治(conquer)呢？
我們要求經(jīng)過(guò)root且長(zhǎng)度不超過(guò)K的所有路徑，也就是求所有(deep[u]+deep[v]<=K ----- 1) (u,v不在同一個(gè)root的兒子下面)的點(diǎn)對(duì)(deep[u]是值u到root的距離)
直接求“u,v不屬于同一個(gè)root的兒子”的點(diǎn)對(duì)總數(shù)比較困難，我們可以容斥著做：
ans = (所有滿(mǎn)足1式的點(diǎn)對(duì)) - (root的兒子 a(1...m)下面所有滿(mǎn)足1式的點(diǎn)對(duì)) (計(jì)算m次)
計(jì)算一次所有滿(mǎn)足1式的點(diǎn)對(duì)的方法是
1. 根據(jù)deep值從小到大排序
2. 掃一遍，維護(hù)一個(gè)值left，使left是val[left] + val[i] <=K的最大值
這樣分治的每一層時(shí)間復(fù)雜度是O(NlogN)
一共分治logN層 總復(fù)雜度(N*(logN)^2)
1 #include<iostream>
2 #include<cstdio>
3 #include<cassert>
4 #include<algorithm>
5 using namespace std;
6 #define re(i,n) for(int i=0;i<n;i++)
7 #define re3(i,n) for(int i=1;i<n;i++)
8 int n,e,size,g,len,k,__ANS;
9 const int V = 10005;
10 const int E = V*2;
11 int head[V] , nxt[E] , pnt[E], hash[E], cost[E], sum[V], tmp[V], dep[V];
12 template <typename T> inline
void chkmax(T &a,
const T b) {
if(a < b) a = b;}
13 void dfs(
int u,
int f){
14 sum[u] = 1;
15 bool flag = 0;
16 for(
int i = head[u]; i != -1; i = nxt[i]){
17 if(hash[i])
continue;
18 int v = pnt[i];
19 if(v == f)
continue;
20 dfs(v,u);
21 if(sum[v] > size /2) flag = 1;
22 sum[u] += sum[v];
23 // cout<<"u: "<<u<<" v: "<<v<<" "<<sum[v]<<endl;
24 }
25 if(!flag && sum[u] > size/2) g = u;
26 // cout<<"u: "<<u<<" "<<sum[u]<<endl;
27 }
28 void dfs1(
int u,
int f,
int d){
29 dep[u] = d;
30 tmp[len++] = d;
31 for(
int i = head[u]; i!= -1;i=nxt[i]){
32 if(hash[i])
continue;
33 int v = pnt[i];
34 if(v == f)
continue;
35 dfs1(v,u,d+ cost[i]);
36 }
37 }
38 void dfs2(
int u,
int f){
39 tmp[len++] = dep[u];
40 for(
int i = head[u]; i!=-1; i=nxt[i]){
41 if(hash[i])
continue;
42 int v = pnt[i];
43 if(v!=f) dfs2(v,u);
44 }
45 }
46 int cal_SUM(){
47 int SUM = 0,l=0;
48 sort(tmp,tmp+len);
49 // re(i,len) cout<<tmp[i]<<" "; cout<<endl;
50 re3(i,len){
51 while(tmp[l]+tmp[i]>k) l --;
52 l ++;
53 SUM += l;
54 }
55 // cout<<"SUM: "<<SUM<<endl;
56 return SUM;
57 }
58 int dfs3(
int u,
int f){
59 sum[u] = 1;
60 for(
int i= head[u];i!=-1;i=nxt[i]){
61 if(hash[i] || pnt[i]==f)
continue;
62 else sum[u] += dfs3(pnt[i],u);
63 }
64 return sum[u];
65 }
66 void cal(
int x,
int s){
67 g = -1, size = s;
68 // cout<<x<<" "<<s<<endl;
69 dfs(x,x);
70 assert(g>=0);
71 // cout<<g<<endl;
72 //// find zhongxin
73 len = 0;
74 dfs1(g,g,0);
75 assert(len == size);
76 int SUM = cal_SUM();
77 for(
int i = head[g]; i!=-1; i=nxt[i]){
78 if(hash[i])
continue;
79 int v= pnt[i];
80 hash[i] = hash[i^1] = 1;
81 len = 0;
82 dfs2(v,v); SUM -= cal_SUM();
83 hash[i] = hash[i^1] = 0;
84 }
85 __ANS += SUM;
86 // cout<<SUM<<endl;
87 dfs3(g,g);
88 ///// CAL SUM
89 for(
int i = head[g]; i!=-1;i=nxt[i]){
90 if(hash[i])
continue;
91 int v = pnt[i];
92 hash[i] = hash[i^1] = 1;
93 cal(v, sum[v]);
94 hash[i] = hash[i^1] = 0;
95 }
96 // DIVIDE AND CONQURE
97 }
98 void add_edge(
int u,
int v,
int c){
99 nxt[e] = head[u];
100 head[u] = e;
101 pnt[e] = v;
102 cost[e++] = c;
103 }
104 int main(){
105 while(~scanf("%d%d",&n,&k) && !(!n&&!k)){
106 re(i,n) head[i] = -1;
107 int u,v,c;
108 e = 0;
109 re(i,n-1) {
110 scanf("%d%d%d",&u,&v,&c);
111 add_edge(u-1,v-1,c); add_edge(v-1,u-1,c);
112 }
113 __ANS = 0;
114 cal(0,n);
115 printf("%d\n",__ANS);
116 }
117 return 0;
118 }
119 posted on 2012-05-02 16:58
西月弦 閱讀(463)
評(píng)論(0) 編輯 收藏 引用 所屬分類(lèi):
解題報(bào)告 、
經(jīng)典題目