题目描述：
给你一个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
西月弦 阅读(457)
评论(0) 编辑 收藏 引用 所属分类:
解题报告 、
经典题目