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

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

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

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

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

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

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

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#define lson step << 1
#define rson step << 1 | 1
#define pb(a) push_back(a)
#define mp(a,b) make_pair(a , b)
#define lowbit(x) (x & (-x))
#pragma comment(linker, "/STACK:1024000000,1024000000")
using namespace std;
typedef long long LL;
const int N = 100005;
struct Edge {
int v , w , next;
}e[N << 1];
int n , l , w , tot , start[N];
int del[N] = {0} , size[N];
LL ans = 0LL;
void _add (int u , int v , int w) {
e[tot].v = v ; e[tot].next = start[u];
e[tot].w = w;
start[u] = tot ++;
}
void add (int u , int v , int w) {
_add (u , v , w);
_add (v , u , w);
}
void calsize (int u , int pre) {
size[u] = 1;
for (int i = start[u] ; i != -1 ; i = e[i].next) {
int v = e[i].v;
if (v == pre || del[v]) continue;
calsize (v , u);
size[u] += size[v];
}
}
int totalsize , maxsize , rootidx;
void dfs (int u , int pre) {
int mx = totalsize - size[u];
for (int i = start[u] ; i != -1 ; i = e[i].next) {
int v = e[i].v;
if (v == pre || del[v]) continue;
mx = max (mx , size[v]);
dfs (v , u);
}
if (mx < maxsize) maxsize = mx , rootidx = u;
}
int search (int r) {
calsize (r , -1);
totalsize = size[r];
maxsize = 1 << 30;
dfs (r , -1);
return rootidx;
}
vector<pair<int,int> > sub[N] , all;
int idx , dist[N] , cnt[N];
void gao (int u , int pre) {
all.pb(mp(dist[u] , cnt[u]));
sub[idx].pb(mp(dist[u] , cnt[u]));
for (int i = start[u] ; i != -1 ; i = e[i].next) {
int v = e[i].v , w = e[i].w;
if (v == pre || del[v]) continue;
dist[v] = dist[u] + w;
cnt[v] = cnt[u] + 1;
gao (v , u);
}
}
int s[N] , up;
void add (int x , int val) {
for (int i = x ; i <= up ; i += lowbit (i)) {
s[i] += val;
}
}
int ask (int x) {
int ret = 0;
for (int i = x ; i > 0 ; i -= lowbit (i)) {
ret += s[i];
}
return ret;
}
LL fuck (vector<pair<int , int> > &v) {
LL ret = 0;
up = 0;
for (int i = 0 ; i < v.size() ; i ++)
up = max (up , v[i].second);
for (int i = 1 ; i <= up ; i ++)
s[i] = 0;
for (int i = 0 ; i < v.size() ; i ++)
add (v[i].second , 1);
for (int i = 0 , j = v.size() - 1 ; i < v.size() ; i ++) {
while (j >= i && v[i].first + v[j].first > w) {
add (v[j].second , -1);
j --;
}
if (j < i) break;
ret += ask (min(up , (l - v[i].second)));
add (v[i].second , -1);
}
return ret;
}
void solve (int root) {
root = search (root);
del[root] = 1;
if (totalsize == 1) return ;
idx = 0 ;all.clear();
for (int i = start[root] ; i != -1 ; i = e[i].next) {
int v = e[i].v , w = e[i].w;
if (del[v]) continue;
sub[idx].clear();
dist[v] = w ; cnt[v] = 1;
gao (v , -1);
sort (sub[idx].begin() , sub[idx].end());
idx ++;
}
sort (all.begin() , all.end());
ans += fuck (all);
for (int i = 0 ; i < idx ; i ++) {
for (int j = 0 ; j < sub[i].size() ; j ++) {
if (sub[i][j].first <= w && sub[i][j].second <= l) {
ans ++;
}
}
ans -= fuck (sub[i]);
}
for (int i = start[root] ; i != -1 ; i = e[i].next) {
int v = e[i].v;
if (del[v]) continue;
solve (v);
}
}
int main () {
// freopen ("input.txt" , "r" , stdin);
// freopen ("output.txt" , "w" , stdout);
tot = 0;memset (start , -1 , sizeof(start));
scanf ("%d %d %d" , &n , &l , &w);
for (int i = 1 ; i < n ; i ++) {
int p , d;
scanf ("%d %d" , &p , &d);
add (i + 1 , p , d);
}
solve (1);
printf ("%I64d\n" , ans);
return 0;
}

最新文章

  1. KMP算法 hdu4686 Oulipo
  2. linux下压缩与解压(zip、unzip、tar)详解
  3. PHP声明
  4. window.onload,&lt;body onload=&quot;function()&quot;&gt;, document.onreadystatechange, httpRequest.onreadystatechang
  5. HTML与CSS入门——第三章 理解HTML和XHTML的关系
  6. OutputCache祥解
  7. token鉴权的一种实现方式图解
  8. php封装curl,模拟POST和GET请求HTTPS请求
  9. python 如何把小数变成百分数格式
  10. 谈一谈HashMap类
  11. hadoop本地集群搭建
  12. Nginx + Tomcat搭建集群
  13. python中的分号
  14. Android Migrate Android Code
  15. X-Forwarded-For 会少记录一次代理服务器的IP
  16. e611. Setting Focus Traversal Keys for the Entire Application
  17. HDU 4902 Nice boat 成段线段树
  18. 去掉img标签周围的空白
  19. FTP服务器的搭建与配置
  20. BeginInvoke 方法真的是新开一个线程进行异步调用吗?

热门文章

  1. CRL快速开发框架开源完全转到Github
  2. spring boot(七):springboot+mybatis多数据源最简解决方案
  3. mysql 日期函数总结
  4. 1.3 Makefile 工程管理
  5. rdlc报表DEMO
  6. javascript面向对象(1)
  7. 总结一下工作中用到的Mybatis业务逻辑
  8. IOS线程的一些总结
  9. QQ2013手工去广告
  10. OpenCDN2.0安装
  11. way/XMPP
  12. NET Core 1.0
  13. 一段JAVA代码了解多线程,JUC、CAS原子性操作。
  14. Java开发知识之Java面相对象
  15. python线程join方法
  16. [Coci2015]Divljak
  17. 《口算大作战 2》DLC:算法真奇妙
  18. 实验五分析system_call中断处理过程
  19. python3学习笔记.2.基础
  20. Github上600多个iOS开源项目地址