锐客网

  1. 首页 > 睿知 > it技术 > >

POJ3321 Apple Tree 题解

IT知识apple题解

临文乍了了，彻卷兀若无。这篇文章主要讲述POJ3321 Apple Tree 题解相关的知识，希望能为你提供帮助。
POJ3321 Apple Tree
线段数例题解析合集
题意：给定一棵树，有两种操作：1、把某个节点上的数^1(若是1改为0，是0改为1) 2、查询以某个节点为根节点的子树中1的个数
在一棵树上进行单点修改和查询，只要进行一遍dfs，记录每个点的dfs序即可把问题转化到链上用线段树进行维护
【POJ3321 Apple Tree 题解】更改和模板一样，查询时以每棵子树遍历时第一个节点的dfs序和最后一个节点的边界作为查询区间（每颗子树中节点的DFS序是连续的）

#include < stdio.h> #include < iostream> using namespace std; inline void read (int & x) { char ch = getchar(); x = 0; while (!isdigit(ch)) ch = getchar(); while (isdigit(ch)) x = x * 10 + ch - 48, ch = getchar(); } void print (int x) { if (x > 9) print (x / 10); putchar (x % 10 + 48); } const int N = 1e6 + 10; int n, cnt, tot, m, pos, ql, qr, s[N < < 2], num[N], l[N], r[N], nxt[N < < 1], to[N < < 1], h[N]; inline void add (int u, int v) { to[++tot] = v, nxt[tot] = h[u], h[u] = tot; } void dfs (int u, int la) { num[u] = l[u] = ++ cnt; for (int i = h[u]; i; i = nxt[i]) if (to[i] != la) dfs (to[i], u); r[u] = cnt; //l、r记录每颗子树中最小和最大的dfs序 } #define ls p < < 1 #define rs p < < 1 | 1 void build (int p, int l, int r) { if (l == r) {s[p] = 1; return; } int mid (l + r > > 1); build (ls, l, mid), build (rs, mid + 1, r); s[p] = s[ls] + s[rs]; } void change (int p, int l, int r) { if (l == r) {s[p] ^= 1; return; } //把0改为1，把1改为0，相当于当前数字^1 int mid (l + r > > 1); pos < = mid ? change (ls, l, mid) : change (rs, mid + 1, r); s[p] = s[ls] + s[rs]; } int query (int p, int l, int r) { if (ql < = l & & qr > = r) return s[p]; int mid (l + r > > 1), t (0); if (ql < = mid) t += query (ls, l, mid); if (qr > mid) t += query (rs, mid + 1, r); return t; } int main() { read (n); for (int i = 1, u, v; i < n; ++i) read (u), read (v), add (u, v), add (v, u); dfs (1, 0); build (1, 1, n); read (m); for (int i = 1; i < = m; ++i) { char ch = getchar(); getchar(); if (ch == \'C\') read (pos), pos = num[pos], change (1, 1, n); else read (pos), ql = l[pos], qr = r[pos], print (query (1, 1, n)), puts (""); } return 0; }


    推荐阅读


    上一篇：.net core启用 autoMapper

    下一篇：MyBatis - Mapper动态代理开发