poj3321 Apple Tree dfs序 + 树状数组
题意：
一棵树，每棵树的初始权值为1，现在有两个操作
1. "C x" 改变节点x的权值，1变0，0变1
2."Q x"询问以x为根节点的子树的权值和
题解：
通过dfs序将树上问题转化为区间问题，通过树状数组维护权值和
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> using namespace std; const int N = 1e5 + 10; int n, m, h[N],e[N<<1],ne[N<<1],idx; int L[N],R[N], tot; int cnt[N]; void add(int a,int b) { e[idx] = b, ne[idx] = h[a], h[a] = idx++; } void dfs(int u, int fa) { L[u] = ++tot; for (int i = h[u]; ~i; i = ne[i]) { int j = e[i]; if (j == fa) continue; dfs(j, u); } R[u] = tot; } struct treearray{ int tr[N], kk; int lbt(int x) { return x&(-x); } int ask(int i) { int sum = 0; for (; i; i -= lbt(i)) sum+= tr[i]; return sum; } void add(int i, int x) { for (; i<=kk; i+=lbt(i)) { tr[i] += x; } } void init() { for (int i = 1; i <= n; i++) cnt[i] = 1,add(i,1); } }t; int main() { freopen("in.txt", "r", stdin);freopen("out.txt", "w", stdout); cin >> n; t.kk = n; memset(h, -1, sizeof h); for (int i = 1; i < n; i++) { int a, b; scanf("%d%d", &a, &b); add(a, b), add(b,a); } t.init(); dfs(1, 0); cin >> m; while (m--) { char op[2]; int x; scanf("%s%d", op, &x); if (op[0] == 'Q') printf("%d ", t.ask(R[x]) - t.ask(L[x]-1)); else{ if (cnt[x]) { t.add(L[x], -1); cnt[x] = 0; } else t.add(L[x], 1), cnt[x] = 1; } } }
A - Counting Offspring
题意：给你一棵树，求每个节点的子节点权值比他小的数的个数
题解：先dfs序，然后用树状数组，从小到大往树状数组对应的位置加1；
C - New Year Tree
题意：一棵树，每个节点有一个颜色
两个操作
将以z为根的子树的结点全部更新为颜色X 2，问以z为根的子树的结点的不同颜色数量
题解：dfs序+区间染色需要用， 因为颜色的数量小于60，用Longlong的二进制来表示颜色
#include <iostream> #include <algorithm> #include <cstdio> #include<cstring> #include<bitset> using namespace std; #define scai(x) scanf("%lld", &x); #define scaii(x, y) scanf("%lld%lld", &x, &y); #define ll long long #define int ll #define re read() inline int read(){char tempt = getchar();int x = 0, f = 0;while (tempt < '0' || tempt > '9')f |= tempt == '-', tempt = getchar();while (tempt >= '0' && tempt <= '9')x = x * 10 + tempt - '0', tempt = getchar();return f ? -x : x;} const int N = 4e5 + 10; int a[N]; int L[N], R[N]; int h[N], ne[N << 1], idx, e[N << 1]; int d[N]; int now; struct node { int l, r; long long color; int lazy; } tr[N << 2]; int f(long long x) { bitset<70> a(x); return a.count(); } void pushdown(int u) { if (tr[u].lazy!=-1) { tr[u<<1].color = (1ll<<tr[u].lazy); tr[u<<1|1].color = (1ll<<tr[u].lazy); tr[u<<1].lazy = tr[u].lazy; tr[u<<1|1].lazy = tr[u].lazy; tr[u].lazy = -1; } } void pushup(int u) { tr[u].color = (tr[u<<1].color | tr[u<<1|1].color); } void add(int a, int b) { e[idx] = b; ne[idx] = h[a]; h[a] = idx++; } void dfs(int u, int fa) { L[u] = ++now; d[now] = u; // cout << L[u] << " "; for (int i = h[u]; ~i; i = ne[i]) { int j = e[i]; if (j == fa) continue; dfs(j, u); } R[u] = now; } void build(int u, int l, int r) { if (l == r) { tr[u] = {l, l, 1ll<<a[d[l]], -1}; // cout << l << " " << tr[u].color << endl; return; } else { tr[u] = {l, r, 0ll, -1}; int mid = l + r >> 1; build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r); pushup(u); } } ll query(int u, int l, int r) { if (tr[u].l >= l && tr[u].r <= r) { return tr[u].color; } else{ pushdown(u); int mid = tr[u].l + tr[u].r >> 1; ll v = 0ll; if (l <= mid) v |= query(u<<1, l, r); if (r > mid) v |= query(u<<1|1, l, r); pushup(u); return v; } } void modify(int u, int l, int r, int c) { if (tr[u].l >= l && tr[u].r <= r) { tr[u].lazy = c; tr[u].color = (1ll<<c); // pushup(u); } else { pushdown(u); int mid = tr[u].l + tr[u].r >> 1; if (l <= mid) modify(u<<1, l, r, c); if (r > mid) modify(u<<1|1, l, r, c); pushup(u); } } signed main() { freopen("in.txt", "r", stdin);freopen("out.txt","w", stdout); int n, m; memset(h, -1, sizeof h); scanf("%lld%lld", &n, &m); for (int i = 1; i <= n; i++) { a[i] = re; } for (int i = 1; i < n; i++) { int a, b; a = re, b = re; add(a, b), add(b, a); } dfs(1, 0); build(1, 1, n); while (m--) { int op, z; op = re, z = re; if (op == 1) { int x; scai(x); modify(1, L[z], R[z], x); } else { printf("%lld ", f(query(1, L[z], R[z]))); } } }
A Party for You Started
题意：每次给树上一个节点增加一个值，询问某个节点到根节点的权值和
方法一：
题解：
还是先dfs序将数展开，用线段数为何每个节点到根节点的和，如果一个节点的值加上一个k，相当于以这个节点为根节点的子树的所有节点加上一个k，这样就转化为线段树区间染色和单点查询问题
方法二：
题解：
这题还可以用欧拉序+树状数组维护前缀和
欧拉序进的地方加v，出的地方减v每次询问求进的地方的前缀和
#include <iostream> #include <algorithm> #include <cstdio> #include<cstring> #include<bitset> using namespace std; #define scai(x) scanf("%lld", &x); #define scaii(x, y) scanf("%lld%lld", &x, &y); #define ll long long #define int ll #define re read() inline int read(){char tempt = getchar();int x = 0, f = 0;while (tempt < '0' || tempt > '9')f |= tempt == '-', tempt = getchar();while (tempt >= '0' && tempt <= '9')x = x * 10 + tempt - '0', tempt = getchar();return f ? -x : x;} #define STDIN freopen("in.txt","r",stdin); freopen("out.txt","w",stdout);//************************************ const int N = 4e4 + 10; int L[N<<2], R[N<<2]; int euler[N<<2],cnt; int h[N<<2], ne[N<<2], e[N<<2], idx; int n, m; void add(int a, int b) { e[idx] = b; ne[idx] = h[a]; h[a] = idx++; } void dfs(int u, int fa) { euler[++cnt] = u; L[u] = cnt; for (int i = h[u]; ~i; i = ne[i]) { int j = e[i]; if (j == fa) continue; dfs(j, u); } euler[++cnt] = u; R[u] = cnt; } struct treearray{ int kk, tr[N]; int lbt(int x) { return x & (-x); } void add(int i, int v) { for (; i <= kk; i += lbt(i)) tr[i] += v; } int ask(int i) { int sum = 0; for (; i; i -= lbt(i)) sum += tr[i]; return sum; } }t; signed main() { STDIN memset(h, -1, sizeof h); scaii(n, m); for (int i = 1; i <= n; i++) { int t; scai(t); add(t, i), add(i, t); } dfs(0,-1); t.kk = cnt; for (int i = 1; i <= m; i++) { int u, x, v; scaii(u, x); scai(v); printf("%lld ", t.ask(L[v])); t.add(L[u],x); t.add(R[u],-x); } }
方法二
#include <iostream> #include <algorithm> #include <cstdio> #include<cstring> #include<bitset> using namespace std; #define scai(x) scanf("%lld", &x); #define scaii(x, y) scanf("%lld%lld", &x, &y); #define ll long long #define int ll #define re read() inline int read(){char tempt = getchar();int x = 0, f = 0;while (tempt < '0' || tempt > '9')f |= tempt == '-', tempt = getchar();while (tempt >= '0' && tempt <= '9')x = x * 10 + tempt - '0', tempt = getchar();return f ? -x : x;} #define STDIN freopen("in.txt","r",stdin); freopen("out.txt","w",stdout);//************************************ const int N = 2e4 + 10; int e[N<<1], ne[N<<1], idx, h[N]; int n,m,now; int L[N], R[N], d[N]; struct node{ int l, r,sum; int lazy; }tr[N<<4]; void add(int a, int b) { e[idx] = b; ne[idx] = h[a]; h[a] = idx++; } void dfs(int u, int fa) { L[u] = ++now; d[now] = u; for (int i = h[u]; ~i; i = ne[i]) { int j = e[i]; if (j == fa) continue; dfs(j, u); } R[u] = now; } void pushdown(int u) { if (tr[u].lazy > 0) { tr[u<<1].lazy += tr[u].lazy; tr[u<<1|1].lazy += tr[u].lazy; tr[u<<1].sum += tr[u].lazy; tr[u<<1|1].sum += tr[u].lazy; tr[u].lazy = 0; } } void build(int u, int l, int r) { if (l == r) { tr[u] = {l, l, 0,0}; } else { tr[u] = {l, r, 0,0}; int mid = l + r >> 1; build(u<<1, l, mid), build(u<<1|1, mid + 1, r); } } void modify(int u, int l, int r, int v) { if (tr[u].l >= l && tr[u].r <= r) { tr[u].sum+=v; tr[u].lazy += v; } else{ pushdown(u); int mid = tr[u].l + tr[u].r >> 1; if (l <= mid) modify(u<<1, l, r, v); if (r > mid) modify(u<<1|1, l, r, v); } } int query(int u, int x) { if (tr[u].l == x && tr[u].r == x) { return tr[u].sum; } else{ pushdown(u); int mid = tr[u].l+tr[u].r >> 1; int v = 0; if (x <= mid) return query(u<<1, x); if (x > mid) return query(u<<1|1, x); } } signed main() { STDIN memset(h, -1, sizeof h); scaii(n, m); for (int i = 1; i <= n; i++) { int t; scai(t); add(t, i), add(i, t); } dfs(0,-1); build(1,1,n+1); for (int i = 1; i <= m; i++) { int l, v, x; scaii(l, v); scai(x); printf("%lld ", query(1, L[x])); modify(1, L[l], R[l], v); } }