题意
给出一棵树，和树上两点之间的边权大小，要你快速回答出树上有多少不同的点对使的这对点之间的距离至多为k。
思路
典型的点分治问题。
当考虑一棵有根树中有多少点对的距离小于等于k时，可以求出所有节点到根部的距离，然后使用二分，或者尺取的方法得到有多少对点之间的距离小于等于k。但是在上面的计算过程中我们想要求的是经过根部的符合要求的点对数量，但实际上多算入了一些并不符合要求的点，同时也漏掉了不经过根部的符合条件的点对。
所以我们可以这样看：一棵树的符合条件点对数=上面所述方法找出的点对数-各个子树中两点间距小于等于(k-2e)的点对数目(e是根部到孩子的树边的边权)+各个子树符合条件的点对数
上面的式子是递归的，这是一个树分治（点分治）策略。
在实现树分治的时候，一定要注意只有配合了重心的点分治才能达到O(nlogn)的复杂度，否则会面临特殊情况（比如链）退化到O(n^2).
代码
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 |
#include <iostream> #include <algorithm> #include <queue> #include <vector> #include <cstdlib> #include <cstdio> #include <string> #include <cstring> #include <ctime> #include <iomanip> #include <cmath> #include <set> #include <stack> #include <cmath> #include <map> #include <complex> using namespace std; const int MAXV = 40005; const int MAXE = 80005; int N,M,K; int head[MAXV],nxt[MAXE],to[MAXE],len[MAXE],vis[MAXV],gphtot; void gph_init(){ gphtot = 2; memset(head,0,sizeof(head)); memset(vis,0,sizeof(vis)); } void gph_addEdge(int from,int _to,int cost){ to[gphtot] = _to; nxt[gphtot] = head[from]; len[gphtot] = cost; head[from] = gphtot++; } void input(){ scanf(" %d %d",&N,&M); gph_init(); for(int i = 1; i <= M; i++){ int a,b,c; char d; scanf(" %d %d %d %c",&a,&b,&c,&d); gph_addEdge(a,b,c); gph_addEdge(b,a,c); } scanf(" %d",&K); } int siz[MAXV],mic,bal; void getbal(int cur,int par,int totsiz){ int mxc = 0; siz[cur] = 1; for(int j = head[cur]; j; j = nxt[j]){ int now = to[j]; if(now != par && !vis[now]){ getbal(now,cur,totsiz); siz[cur] += siz[now]; mxc = max(mxc,siz[now]); } } mxc = max(mxc,totsiz - siz[cur]); if(mic > mxc){ mic = mxc; bal = cur; } } int dis[MAXV],distot; void dfs_dis(int cur,int par,int hav = 0){ dis[distot++] = hav; siz[cur] = 1; for(int j = head[cur]; j; j = nxt[j]){ int now = to[j]; if(now != par && !vis[now]){ dfs_dis(now,cur,hav+len[j]); siz[cur] += siz[now]; } } } int calc(int rt,int k){ distot = 0; dfs_dis(rt,0,k); int ret = 0; sort(dis,dis+distot); int r = distot - 1; for(int l = 0; l < distot; l++){ while(dis[r] + dis[l] > K){ r--; } if(r <= l){ break; } ret += r-l; } return ret; } int res; void dfs_main(int cur){ res += calc(cur,0); vis[cur] = true; for(int j = head[bal]; j; j = nxt[j]){ int now = to[j]; if(!vis[now]){ res -= calc(now,len[j]); mic = 0x3f3f3f3f; getbal(now,cur,siz[now]); dfs_main(bal); } } } void solve(){ res = 0; mic = 0x3f3f3f3f; getbal(1,0,N); dfs_main(bal); printf("%d\n",res); } int main(){ input(); solve(); } |
December 06, 2015
[…] 和这个题非常像，只不过题意从计算有多少点对之间距离小于k换成了判断有没有一条路径等于k。但实际上可以用一套思路解决。 […]