codeforces 570D Tree Requests

2019-11-08 18:23:58

字体：大中小

来源：转载

供稿：网友

题目链接

分析:

之前学习到了一种做法，将树上的dfs序和bfs序都计算出来，主要用到bfs序。通过bfs序可以找到对应层数的所有节点，然后通过dfs序范围确定符合要求节点的范围长度，这一点可以用二分来确定左右区间范围。然后就是判断区间里的字母个数为奇的是否小于等于1。我用了数组预处理了每个字母的前缀和，在写题解的时候想到可以用int二进制表示。

代码：

/*****************************************************///#PRagma comment(linker, "/STACK:1024000000,1024000000")#include <map>#include <set>#include <stack>#include <queue>#include <cmath>#include <string>#include <vector>#include <cstdio>#include <cstring>#include <sstream>#include <cstdlib>#include <iostream>#include <algorithm>using namespace std;#define offcin ios::sync_with_stdio(false)#define DEBUG freopen("#.txt", "r", stdin)#define sigma_size 26#define lson l,m,v<<1#define rson m+1,r,v<<1|1#define slch v<<1#define srch v<<1|1#define ll long long#define ull unsigned long long#define lowbit(x) (x&-x)const int INF = 0x3f3f3f3f;const ll INFF = 1e18;const double pi = acos(-1.0);const double inf = 1e18;const double eps = 1e-9;const ll mod = 1e9+7;const int maxmat = 10;const ull BASE = 133333331;/*****************************************************/inline void RI(int &x) { char c; while((c=getchar())<'0' || c>'9'); x=c-'0'; while((c=getchar())>='0' && c<='9') x=(x<<3)+(x<<1)+c-'0';}inline ll bits(ll x) { return !x ? x : bits(x - lowbit(x)) + 1;}/*****************************************************/const int maxn = 5e5 + 5;char str[maxn];std::vector<int> G[maxn];int pre[maxn], ed[maxn], par[maxn], d[maxn];int dfs_time;int sum[maxn][30];struct Node { int id, dep, num;}node[maxn];struct Range{ int l, r;}r[maxn];int getl(int l, int r, int x) { int lb = l, ub = r, res = -1; while (lb <= ub) { int mid = (lb + ub ) >> 1; if (node[mid].num >= x) { res = mid; ub = mid - 1; } else lb = mid + 1; } return res;}int getr(int l, int r, int x) { int lb = l, ub = r, res = -1; while (lb <= ub) { int mid = (lb + ub) >> 1; if (node[mid].num <= x) { res = mid; lb = mid + 1; } else ub = mid - 1; } return res;}bool query(int L, int R) { int tmp, ans = 0; for (int i = 0; i < 26; i ++) { tmp = sum[R][i] - sum[L - 1][i]; ans += (tmp & 1); } return ans <= 1;}void dfs(int u, int fa, int dep) { pre[u] = ++ dfs_time; d[u] = dep; for (int v : G[u]) if (v != fa) dfs(v, u, dep + 1); ed[u] = dfs_time;}void bfs() { std::queue<pair<int, pair<int, int> > > q; q.push(make_pair(1, make_pair(1, 1))); int cnt = 0; while (!q.empty()) { auto x = q.front(); q.pop(); node[++ cnt] = Node{x.first, x.second.first, x.second.second}; int u = x.first; for (int v : G[u]) if (v != par[u]) q.push(make_pair(v, make_pair(x.second.first + 1, pre[v]))); } int s = 0; int L = 0, R = 0; for (int i = 1; i <= cnt; i ++) { for (int j = 0; j < 26; j ++) sum[i][j] = sum[i - 1][j] + (str[node[i].id] - 'a' == j); if (node[i].dep != node[i - 1].dep) { r[s ++] = Range{L - 1, R - 1}; L = i + 1, R = L; } else R ++; } r[s] = Range{L - 1, R - 1};}int main(int argc, char const *argv[]) { //DEBUG; int N, M; cin>>N>>M; for (int i = 2; i <= N; i ++) { scanf("%d", par + i); G[par[i]].push_back(i); G[i].push_back(par[i]); } scanf("%s", str + 1); dfs(1, -1, 1); bfs(); while (M --) { int v, h; scanf("%d%d", &v, &h); int L = getl(r[h].l, r[h].r, pre[v]); int R = getr(r[h].l, r[h].r, ed[v]); if (L == -1 || R == -1) puts("Yes"); else { if (query(L, R)) puts("Yes"); else puts("No"); } } return 0;}

上一篇：2.1、注释符号

下一篇：spring动态加载数据源