首页 > 代码库 > [bzoj1103][POI2007]大都市meg
[bzoj1103][POI2007]大都市meg
题意:给定一棵n个点的树,一开始边权都是1,然后要支持修改一条边为0和查询一个点到点1的路上的边权和。n<=250000
题解:求出dfs序,然后每个点如果它和父亲的连边有权值就把它这个子树都+1.
#include<cstdio> #include<iostream> #define INF 2000000000 #define N 262144 using namespace std; inline int read() { int x=0,f=1;char ch=getchar(); while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘) f=-1;ch=getchar();} while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘; ch=getchar();} return x*f; } char c[10]; int n,m,cnt=0,s[250005],nl[250005],nr[250005],head[250005]; struct edge{ int to,next; }e[250005]; void ins(int f,int t){e[++cnt].next=head[f];head[f]=cnt;e[cnt].to=t;} void renew(int x,int ad){for(;x<=n;x+=x&(-x)) s[x]+=ad;} int query(int x){int sum=0;for(;x>0;x-=x&(-x))sum+=s[x];return sum;} void dfs(int x){nl[x]=++cnt;for(int i=head[x];i;i=e[i].next)dfs(e[i].to);nr[x]=cnt;} int main() { n=read(); for(int i=1;i<n;i++) {int u=read(),v=read();ins(u,v);} cnt=0;dfs(1);m=read(); for(int i=2;i<=n;i++) renew(nl[i],1),renew(nr[i]+1,-1); while(m) { scanf("%s",c); if(c[0]==‘A‘){int l=read(),r=read();if(l>r)swap(l,r);renew(nl[r],-1);renew(nr[r]+1,1);} else printf("%d\n",query(nl[read()])),--m; } return 0; }
[bzoj1103][POI2007]大都市meg
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。