題目描述：
給你一個N(N<10000)個點的有權樹，請問距離不超過K(K<1,000,000,000)的點對有多少個?
吐槽：
1. 大家想不想看男人八題的總結？ 有需求的話我就一天寫一篇~~~~ (之前切了3道...不過寫的很挫)
2. 代碼寫的很挫，加上各種注釋/調試語句干了2.5k...
3. 說好的今天學塊鏈呢...
算法分析：
又是一道計數問題，總的想法是分治然后容斥...
對于一個有根樹，計算路徑經過root的點對的個數。如果被計算出來了，再去計算它的子樹。
問題是如何保證它的子樹分布的比較“均勻”呢？ 有個定理：
存在一個點使得分出的子樹的結點個數均不大于 N / 2 (證明略)
我們的目的就是找到一個這樣的點，即樹的重心(可能有多個)。
做法就是從任意一點開始做樹形DP，對于某個點u判斷每個子樹的sum值和SUM-sum[u]的值是否全部不大于n/2...
分(divide)的問題解決了，那么如果治(conquer)呢？
我們要求經過root且長度不超過K的所有路徑，也就是求所有(deep[u]+deep[v]<=K ----- 1) (u,v不在同一個root的兒子下面)的點對(deep[u]是值u到root的距離)
直接求“u,v不屬于同一個root的兒子”的點對總數比較困難，我們可以容斥著做：
ans = (所有滿足1式的點對) - (root的兒子 a(1...m)下面所有滿足1式的點對) (計算m次)
計算一次所有滿足1式的點對的方法是
1. 根據deep值從小到大排序
2. 掃一遍，維護一個值left，使left是val[left] + val[i] <=K的最大值
這樣分治的每一層時間復雜度是O(NlogN)
一共分治logN層 總復雜度(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)
評論(0) 編輯 收藏 引用 所屬分類:
解題報告 、
經典題目