Apple Tree: http://poj.org/problem?id=3321
题意:
告诉你一棵树, 每棵树开始每个点上都有一个苹果, 有两种操作, 一种是计算以 x 为根的树上有几个苹果, 一种是转换 x 这个点上的苹果, 就是有就去掉, 没有就加上.
思路:
先对树求一遍 dfs 序, 每个点保存一个 l,r.l 是最早到这个点的时间戳, r 是这个点子树中的最大时间戳, 这样就转化为区间问题, 可以用树状数组, 或线段树维护区间的和.
- #include <algorithm>
- #include <iterator>
- #include <iostream>
- #include <cstring>
- #include <cstdlib>
- #include <iomanip>
- #include <bitset>
- #include <cctype>
- #include <cstdio>
- #include <string>
- #include <vector>
- #include <stack>
- #include <cmath>
- #include <queue>
- #include <list>
- #include <map>
- #include <set>
- #include <cassert>
- using namespace std;
- //#pragma GCC optimize(3)
- //#pragma comment(linker, "/STACK:102400000,102400000") //c++
- // #pragma GCC diagnostic error "-std=c++11"
- // #pragma comment(linker, "/stack:200000000")
- // #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
- // #pragma GCC optimize("-fdelete-null-pointer-checks,inline-functions-called-once,-funsafe-loop-optimizations,-fexpensive-optimizations,-foptimize-sibling-calls,-ftree-switch-conversion,-finline-small-functions,inline-small-functions,-frerun-cse-after-loop,-fhoist-adjacent-loads,-findirect-inlining,-freorder-functions,no-stack-protector,-fpartial-inlining,-fsched-interblock,-fcse-follow-jumps,-fcse-skip-blocks,-falign-functions,-fstrict-overflow,-fstrict-aliasing,-fschedule-insns2,-ftree-tail-merge,inline-functions,-fschedule-insns,-freorder-blocks,-fwhole-program,-funroll-loops,-fthread-jumps,-fcrossjumping,-fcaller-saves,-fdevirtualize,-falign-labels,-falign-loops,-falign-jumps,unroll-loops,-fsched-spec,-ffast-math,Ofast,inline,-fgcse,-fgcse-lm,-fipa-sra,-ftree-pre,-ftree-vrp,-fpeephole2",3)
- #define lson (l , mid , rt <<1)
- #define rson (mid + 1 , r , rt << 1 | 1)
- #define debug(x) cerr << #x << "=" << x << "\n";
- #define pb push_back
- #define pq priority_queue
- #define max3(a,b,c) max(max(a,b),c)
- typedef long long ll;
- typedef unsigned long long ull;
- typedef pair<ll ,ll> pll;
- typedef pair<int ,int> pii;
- typedef pair<int,pii> p3;
- //priority_queue<int> q;// 这是一个大根堆 q
- //priority_queue<int,vector<int>,greater<int>>q;// 这是一个小根堆 q
- #define fi first
- #define se second
- //#define endl '\n'
- #define OKC ios::sync_with_stdio(false);cin.tie(0)
- #define FT(A,B,C) for(int A=B;A <= C;++A) // 用来压行
- #define REP(i , j , k) for(int i = j ; i <k ; ++i)
- //priority_queue<int ,vector<int>, greater<int>>que;
- const ll mos = 0x7FFFFFFF; //2147483647
- const ll nmos = 0x80000000; //-2147483648
- const int inf = 0x3f3f3f3f;
- const ll inff = 0x3f3f3f3f3f3f3f3f; //18
- const int mod = 1e9+7;
- const double esp = 1e-8;
- const double PI=acos(-1.0);
- template<typename T>
- inline T read(T&x){
- x=0;int f=0;char ch=getchar();
- while (ch<'0'||ch>'9') f|=(ch=='-'),ch=getchar();
- while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
- return x=f?-x:x;
- }
- /*-----------------------showtime----------------------*/
- const int maxn = 300009;
- struct edge
- {
- int to,nx;
- }e[maxn];
- int h[maxn],all;
- void addedge(int u,int v){
- e[all].to = v;
- e[all].nx = h[u];
- h[u] = all++;
- }
- int sum[maxn],vis[maxn];
- char op[20];
- struct node
- {
- int l,r;
- }a[maxn];
- int tot = 1;
- void dfs(int x,int fa){
- a[x].l = tot;
- for(int i=h[x]; ~i; i = e[i].nx){
- int v = e[i].to;
- tot++;
- if(v!=fa){
- dfs(v,x);
- }
- }
- a[x].r = ++tot;
- }
- int lowbit(int x){
- return x&(-x);
- }
- void add(int x,int c){
- while(x <maxn){
- sum[x] += c;
- x += lowbit(x);
- }
- }
- int getsum(int x){
- int res = 0;
- while(x>0){
- res += sum[x];
- x -= lowbit(x);
- }
- return res;
- }
- int main(){
- int n,m,x;
- scanf("%d", &n);
- memset(h,-1,sizeof(h));
- for(int i=1; i<n; i++){
- int u,v;
- scanf("%d%d",&u, &v);
- addedge(u,v);
- addedge(v,u);
- }
- dfs(1,-1);
- for(int i=1; i<=n; i++){
- vis[i] = 1;
- add(a[i].l , 1);
- }
- scanf("%d", &m);
- while(m--){
- scanf("%s%d", op,&x);
- if(op[0] == 'Q'){
- printf("%d\n", getsum(a[x].r) - getsum(a[x].l-1));
- }
- else {
- if(vis[x] == 1){
- add(a[x].l,-1);
- vis[x] = 0;
- }
- else {
- add(a[x].l,1);
- vis[x] = 1;
- }
- }
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2765346.html