首页 > 代码库 > BZOJ 2783 JLOI 2012 树 倍增+二分
BZOJ 2783 JLOI 2012 树 倍增+二分
题目大意:给出一棵树和一个整数s,问在树上有几条这样路径,保证路径上的点权和==s,点的深度递增。输出这个数量。
思路:利用倍增的思想,我们能在O(logn)的时间内求出一个点到他的第n个爸爸之间所有点的点权之和。由于点权只能是正的,满足二分性质。然后对于每一个点二分,看看有没有路径的权值和是S,统计答案,输出。
CODE:
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define MAX 100010 using namespace std; int points,s; int src[MAX]; int head[MAX],total; int next[MAX << 1],aim[MAX << 1]; int father[MAX][20],length[MAX][20]; inline void Add(int x,int y); void DFS(int x,int last); void SparseTable(); inline bool Judge(int x); inline int GetLength(int x,int deep); int main() { cin >> points >> s; for(int i = 1;i <= points; ++i) scanf("%d",&src[i]); for(int x,y,i = 1;i < points; ++i) { scanf("%d%d",&x,&y); Add(x,y),Add(y,x); } DFS(1,0); SparseTable(); int ans = 0; for(int i = 1;i <= points; ++i) ans += Judge(i); cout << ans << endl; return 0; } inline void Add(int x,int y) { next[++total] = head[x]; aim[total] = y; head[x] = total; } void DFS(int x,int last) { father[x][0] = last; length[x][0] = src[last]; for(int i = head[x];i;i = next[i]) { if(aim[i] == last) continue; DFS(aim[i],x); } } void SparseTable() { for(int j = 1;j <= 19; ++j) for(int i = 1;i <= points; ++i) { father[i][j] = father[father[i][j - 1]][j - 1]; length[i][j] = length[i][j - 1] + length[father[i][j - 1]][j - 1]; } } inline bool Judge(int x) { int l = 0,r = 100000; while(l <= r) { int mid = (l + r) >> 1; int length = GetLength(x,mid) + src[x]; if(length < s) l = mid + 1; else if(length > s) r = mid - 1; else return true; } return false; } inline int GetLength(int x,int deep) { int re = 0; for(int i = 19; ~i; --i) if(deep - (1 << i) >= 0) { deep -= 1 << i; re += length[x][i]; x = father[x][i]; } return re; }
BZOJ 2783 JLOI 2012 树 倍增+二分
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。