首页 > 代码库 > [BZOJ 1103][POI 2007]大都市(DFS求拓扑序+树状数组)
[BZOJ 1103][POI 2007]大都市(DFS求拓扑序+树状数组)
题目链接:http://www.lydsy.com:808/JudgeOnline/problem.php?id=1103
题目大意:给你一个树,刚开始所有树边边权均为1,不断地将其中的某些边边权改为0,其间问你某个点到根节点之间路径上的边权和。
此题和POJ的Apple Tree很相近。。。
首先DFS生成整棵树的拓扑序,DFS时每个结点i进入的时间l[i]和离开的时间r[i],然后对每次更改操作,维护树状数组即可。
#include <iostream> #include <stdio.h> #include <stdlib.h> #include <string.h> #include <algorithm> #define MAXE 501000 #define MAXV 251000 #define lowbit(x) (x&(-x)) using namespace std; struct edge { int u,v,next; }edges[MAXE]; int head[MAXV],nCount=0; int sum[MAXE],cnt=0,l[MAXV],r[MAXV],fa[MAXV]; //l、r是每个结点dfs序的左右区间 int n,m; bool visit[MAXV]; void AddEdge(int U,int V) { edges[++nCount].u=U; edges[nCount].v=V; edges[nCount].next=head[U]; head[U]=nCount; } void update(int x,int v) { while(x<MAXE) { sum[x]+=v; x+=lowbit(x); } } int query(int x) { int ans=0; while(x>0) { ans+=sum[x]; x-=lowbit(x); } return ans; } void dfs(int u) //从点u出发dfs,得到树的拓扑序 { visit[u]=true; l[u]=++cnt; update(cnt,1); for(int p=head[u];p!=-1;p=edges[p].next) { int v=edges[p].v; if(!visit[v]) { fa[v]=u; dfs(v); } } r[u]=++cnt; update(cnt,-1); } int main() { memset(head,-1,sizeof(head)); char cmd[10]; scanf("%d",&n); for(int i=1;i<n;i++) { int a,b; scanf("%d%d",&a,&b); AddEdge(a,b); AddEdge(b,a); } dfs(1); scanf("%d",&m); for(int i=1;i<=n+m-1;i++) { int a,b; scanf("%s%d",cmd,&a); if(cmd[0]=='A') //将a-b边边权变为0 { scanf("%d",&b); if(fa[a]==b) swap(a,b); //保证b的父亲是a update(l[b],-1); update(r[b],1); } else printf("%d\n",query(l[a])-1); } return 0; }
[BZOJ 1103][POI 2007]大都市(DFS求拓扑序+树状数组)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。