现在的位置: 首页 > 综合 > 正文

CF 293 E Close Vertices (树的分治+树状数组)

2017年09月28日 ⁄ 综合 ⁄ 共 4319字 ⁄ 字号 小 中 大 ⁄ 评论关闭
分类： ACM_杂物2013-08-09
20:35 486人阅读 评论(6) 收藏 举报

转载请注明出处，谢谢http://blog.csdn.net/ACM_cxlove?viewmode=contents    by---cxlove

题目：给出一棵树，问有多少条路径权值和不大于w，长度不大于l。

http://codeforces.com/contest/293/problem/E

有男人八题很相似，但是多了一个限制。

同样 还是点分治，考虑二元组(到根的路径权值和，到根的路径长度)。

按第一维度排序之后，可以用two points查询权值小不大于w的，然后 用树状数组维护路径长度。

也就是第一个条件用two points，第二个条件用树状数组维护。

[cpp] view
plaincopy

  1. #include <iostream>  
  2. #include <cstdio>  
  3. #include <cstring>  
  4. #include <algorithm>  
  5. #include <vector>  
  6. #define lson step << 1  
  7. #define rson step << 1 | 1  
  8. #define pb(a) push_back(a)  
  9. #define mp(a,b) make_pair(a , b)  
  10. #define lowbit(x) (x & (-x))  
  11. #pragma comment(linker, "/STACK:1024000000,1024000000")      
  12. using namespace std;  
  13. typedef long long LL;  
  14. const int N = 100005;  
  15. struct Edge {  
  16.     int v , w , next;  
  17. }e[N << 1];  
  18. int n , l , w , tot , start[N];  
  19. int del[N] = {0} , size[N];  
  20. LL ans = 0LL;  
  21. void _add (int u , int v , int w) {  
  22.     e[tot].v = v ; e[tot].next = start[u];  
  23.     e[tot].w = w;  
  24.     start[u] = tot ++;  
  25. }  
  26. void add (int u , int v , int w) {  
  27.     _add (u , v , w);  
  28.     _add (v , u , w);  
  29. }  
  30. void calsize (int u , int pre) {  
  31.     size[u] = 1;  
  32.     for (int i = start[u] ; i != -1 ; i = e[i].next) {  
  33.         int v = e[i].v;  
  34.         if (v == pre || del[v]) continue;  
  35.         calsize (v , u);  
  36.         size[u] += size[v];  
  37.     }  
  38. }  
  39. int totalsize , maxsize , rootidx;  
  40. void dfs (int u , int pre) {  
  41.     int mx = totalsize - size[u];  
  42.     for (int i = start[u] ; i != -1 ; i = e[i].next) {  
  43.         int v = e[i].v;  
  44.         if (v == pre || del[v]) continue;  
  45.         mx = max (mx , size[v]);  
  46.         dfs (v , u);  
  47.     }  
  48.     if (mx < maxsize) maxsize = mx , rootidx = u;  
  49. }  
  50. int search (int r) {  
  51.     calsize (r , -1);  
  52.     totalsize = size[r];  
  53.     maxsize = 1 << 30;  
  54.     dfs (r , -1);  
  55.     return rootidx;  
  56. }  
  57. vector<pair<int,int> > sub[N] , all;  
  58. int idx , dist[N] , cnt[N];  
  59. void gao (int u , int pre) {  
  60.     all.pb(mp(dist[u] , cnt[u]));  
  61.     sub[idx].pb(mp(dist[u] , cnt[u]));  
  62.     for (int i = start[u] ; i != -1 ; i = e[i].next) {  
  63.         int v = e[i].v , w = e[i].w;  
  64.         if (v == pre || del[v]) continue;  
  65.         dist[v] = dist[u] + w;  
  66.         cnt[v] = cnt[u] + 1;  
  67.         gao (v , u);  
  68.     }  
  69. }  
  70. int s[N] , up;  
  71. void add (int x , int val) {  
  72.     for (int i = x ; i <= up ; i += lowbit (i)) {  
  73.         s[i] += val;  
  74.     }  
  75. }  
  76. int ask (int x) {  
  77.     int ret = 0;  
  78.     for (int i = x ; i > 0 ; i -= lowbit (i)) {  
  79.         ret += s[i];  
  80.     }  
  81.     return ret;  
  82. }  
  83. LL fuck (vector<pair<int , int> > &v) {  
  84.     LL ret = 0;  
  85.     up = 0;  
  86.     for (int i = 0 ; i < v.size() ; i ++)  
  87.         up = max (up , v[i].second);  
  88.     for (int i = 1 ; i <= up ; i ++)  
  89.         s[i] = 0;  
  90.     for (int i = 0 ; i < v.size() ; i ++)  
  91.         add (v[i].second , 1);  
  92.     for (int i = 0 , j = v.size() - 1 ; i < v.size() ; i ++) {  
  93.         while (j >= i && v[i].first + v[j].first > w) {  
  94.             add (v[j].second , -1);  
  95.             j --;  
  96.         }  
  97.         if (j < i) break;  
  98.         ret += ask (min(up , (l - v[i].second)));  
  99.         add (v[i].second , -1);  
  100.     }  
  101.     return ret;  
  102. }  
  103. void solve (int root) {  
  104.     root = search (root);  
  105.     del[root] = 1;  
  106.     if (totalsize == 1) return ;  
  107.     idx = 0 ;all.clear();  
  108.     for (int i = start[root] ; i != -1 ; i = e[i].next) {  
  109.         int v = e[i].v , w = e[i].w;  
  110.         if (del[v]) continue;  
  111.         sub[idx].clear();  
  112.         dist[v] = w ; cnt[v] = 1;  
  113.         gao (v , -1);  
  114.         sort (sub[idx].begin() , sub[idx].end());  
  115.         idx ++;  
  116.     }  
  117.     sort (all.begin() , all.end());  
  118.     ans += fuck (all);  
  119.     for (int i = 0 ; i < idx ; i ++) {  
  120.         for (int j = 0 ; j < sub[i].size() ; j ++) {  
  121.             if (sub[i][j].first <= w && sub[i][j].second <= l) {  
  122.                 ans ++;  
  123.             }  
  124.         }  
  125.         ans -= fuck (sub[i]);  
  126.     }  
  127.     for (int i = start[root] ; i != -1 ; i = e[i].next) {  
  128.         int v = e[i].v;  
  129.         if (del[v]) continue;  
  130.         solve (v);  
  131.     }  
  132. }  
  133. int main () {  
  134.     // freopen ("input.txt" , "r" , stdin);  
  135.     // freopen ("output.txt" , "w" , stdout);  
  136.     tot = 0;memset (start , -1 , sizeof(start));  
  137.     scanf ("%d %d %d" , &n , &l , &w);  
  138.     for (int i = 1 ; i < n ; i ++) {  
  139.         int p , d;  
  140.         scanf ("%d %d" , &p , &d);  
  141.         add (i + 1 , p , d);  
  142.     }  
  143.     solve (1);  
  144.     printf ("%I64d\n" , ans);  
  145.     return 0;  
  146. }  
返回
【上篇】
【下篇】

作者:

抱歉!评论已关闭.

返回首页

Copyright © 2013-2018 学步园  保留所有权利.
软文销售 QQ客服：2265327166 点击这里给我发消息（其他合作也可洽谈）
必威体育
必威电竞