首页 > 代码库 > HDU - 4366 Successor DFS序 + 分块暴力 or 线段树维护
HDU - 4366 Successor DFS序 + 分块暴力 or 线段树维护
给定一颗树，每个节点都有忠诚和能力两个参数，随意指定一个节点，要求在它的子树中找一个节点代替它，这个节点要满足能力值大于它，而且是忠诚度最高的那个。
首先，dfs一下，处理出L[i], R[i]表示dfs序，则R[i] - L[i] + 1 就是当前i这个节点拥有的子孙个数。
对于一颗树，dfs的时候，访问节点有先后顺序，那么可以用一个struct node List[maxn];表示这课树中访问的先后顺序。
例如这颗树，我假设是先访问0 --> 3 --> 2 ---> 4 ---> 5 ---> 1
这样我用一个List数组保存了，同时记录了L[i]和R[i]。那么对于每次询问删除一个节点cur，就是在[L[cur], R[cur]]里面选择了。例如节点2，L[2] = 2, R[2] = 4。那么就变成了区间最值问题。
分块：块内维护一个数组mx[i]表示当前这个块内能力值 > List[i].ablity的最大忠诚度。想要维护这个，就要开多个数组to_sort[]同样是记录dfs序，但是它要排序，按能力排序，这样可以O(magic)维护完成。
对于每个查询，不在块内的，暴力，在的，二分出一个 > 当前能力的pos，mx[pos]就是答案。
复杂度 O (nsqrt(n) + msqrt(n) * logn)
感觉数据略水，应该用线段树优化掉sqrt(n)
#include <cstdio>#include <cstdlib>#include <cstring>#include <cmath>#include <algorithm>using namespace std;#define inf (0x3f3f3f3f)typedef long long int LL;#include <iostream>#include <sstream>#include <vector>#include <set>#include <map>#include <queue>#include <string>const int maxn = 50000 + 20;struct edge { int u, v, next;} e[maxn * 2];int first[maxn], R[maxn], L[maxn], mx[maxn];int magic;struct node { int abliatly, loyalty ; bool operator < (const node &rhs) const { return abliatly < rhs.abliatly; }} a[maxn], List[maxn], to_sort[maxn];int get_id[1000000 + 20];int n, num;void add (int u, int v){ ++num; e[num].u = u; e[num].v = v; e[num].next = first[u]; first[u] = num;}bool book[maxn];int index;void dfs (int cur){ L[cur] = index; for (int i = first[cur]; i; i = e[i].next) { if (book[e[i].v]) continue; book[e[i].v] = 1; ++index; List[index] = to_sort[index] = a[e[i].v]; dfs (e[i].v); } R[cur] = index;}int find (int begin, int end, int val){ int t = end; if (to_sort[end].abliatly < val) return -1; //不够它大 if (to_sort[begin].abliatly > val) return mx[begin];//bigger while (begin <= end) { int mid = (begin + end) >> 1; if (to_sort[mid].abliatly > val) end = mid - 1; else begin = mid + 1; } if (begin > t) return -1; return mx[begin];}void work (){ int Q; scanf ("%d%d", &n, &Q); magic = (int) sqrt (n * 1.0); for (int i = 1; i <= n - 1; ++i) { int fa, lo, ab; scanf ("%d%d%d", &fa, &lo, &ab); add (fa, i); a[i].abliatly = ab; a[i].loyalty = lo; get_id[lo] = i; } dfs (0); //dfs 构图 for (int i = 0; i < n; i += magic) { int j = i + magic; if (j > n) break; sort (to_sort + i, to_sort + j); mx[j - 1] = to_sort[j - 1].loyalty; for (int k = j - 2; k >= i; --k) { mx[k] = mx[k + 1] > to_sort[k].loyalty ? mx[k + 1] : to_sort[k].loyalty; } } while (Q--) { int id; scanf ("%d", &id); int val = a[id].abliatly; int ans = -inf; int begin = L[id], end = R[id]; for (int i = begin; i <= end;) { if (i % magic == 0 && i + magic - 1 <= end) { int t = find (i, i + magic - 1, val); ans = max (ans, t); i += magic; } else { if (List[i].abliatly > val && ans < List[i].loyalty) { ans = List[i].loyalty; } ++i; } } printf ("%d\n", ans < 0 ? -1 : get_id[ans]); } return ;}int main (){#ifdef local freopen("data.txt","r",stdin);#endif int t; scanf ("%d", &t); a[0].abliatly = -1; a[0].loyalty = -1; List[0] = to_sort[0] = a[0]; while (t--) { work (); memset (first, 0, sizeof first); memset (book, 0, sizeof book); num = 0; index = 0; memset (mx, 0, sizeof mx); } return 0;}
HDU - 4366 Successor DFS序 + 分块暴力 or 线段树维护
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。