首页 > 代码库 > BZOJ 1103 POI 2007 大都市meg 树状数组
BZOJ 1103 POI 2007 大都市meg 树状数组
题目大意:给出一棵树,一开始每两个点之间都是由土路连接的,但是会有一些土路逐渐变成公路,问每次从点1开始到点k有多少土路。
思路:POI不怎么难的题,实际上每个点到1的土路的数量就是这个点的深度,在土路变成公路的时候,这个点以及子树的所有节点的深度都要-1,子树修改就很基本了,可以用DFS序+fenwick,当然要是不嫌麻烦也可以树链剖分,但是常数会比较卡。。
CODE:
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define MAX 250010 using namespace std; int points,asks; int head[MAX],total; int _next[MAX << 1],aim[MAX << 1]; int deep[MAX],cnt; pair<int,int> range[MAX]; int fenwick[MAX]; char c[10]; inline void Add(int x,int y) { _next[++total] = head[x]; aim[total] = y; head[x] = total; } void DFS(int x,int last) { deep[x] = deep[last] + 1; range[x].first = ++cnt; for(int i = head[x]; i; i = _next[i]) { if(aim[i] == last) continue; DFS(aim[i],x); } range[x].second = cnt; } inline void Fix(int x,int c) { for(; x; x -= x&-x) fenwick[x] -= c; } inline int GetSum(int x) { int re = 0; for(; x <= points; x += x&-x) re += fenwick[x]; return re; } int main() { cin >> points; for(int x,y,i = 1; i < points; ++i) { scanf("%d%d",&x,&y); Add(x,y),Add(y,x); } deep[0] = -1; DFS(1,0); cin >> asks; for(int x,y,i = 1; i <= asks + points - 1; ++i) { scanf("%s",c); if(c[0] == 'A') { scanf("%d%d",&x,&y); int opt = deep[x] > deep[y] ? x:y; Fix(range[opt].first - 1,1); Fix(range[opt].second,-1); } else { scanf("%d",&x); printf("%d\n",deep[x] - GetSum(range[x].first)); } } return 0; }
BZOJ 1103 POI 2007 大都市meg 树状数组
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。