题解 P1600 【天天爱跑步】

好像我的思路和大部分题解不一样？  然后我们可以用动态开点权值线段树统计每棵子树内满足上述两个条件的出发点和终点个个数。 然后对于一个点的不同子树，我们可以把他们合并起来。 其他见代码。 ```cpp #include <iostream> #include <algorithm> #include <vector> #include <cmath> #include <assert.h> #include <utility> using int_t = int; using pair_t = std::pair<struct Node *, struct Node *>; using std::cin; using std::cout; using std::endl; // #define DEBUG #define debug(x) std::cout << #x << " = " << x << std::endl; const int_t LARGE = 300000; const int_t INF = 0x7ffffff; const int_t ROOT = 1; std::vector<int_t> graph[LARGE + 1]; int_t n, m; std::vector<int_t> numbers; //欧拉序列处理LCA namespace LCA { int_t count = 0; int_t first[LARGE + 1]; int_t parent[LARGE + 1]; struct Pair { int_t depth; int_t vertex; Pair(int_t depth = -1, int_t vertex = -1) { this->depth = depth; this->vertex = vertex; } } seq[LARGE * 2 + 1][20]; bool operator<(const LCA::Pair &a, const LCA::Pair &b) { return a.depth < b.depth; } void DFS(int_t vertex, int_t depth = 1, int_t from = 0) { parent[vertex] = from; count++; seq[count][0] = Pair{depth, vertex}; if (first[vertex] == 0) { // cout << "first " << vertex << " set to " << count << endl; first[vertex] = count; } for (int_t to : graph[vertex]) { if (to != from) { DFS(to, depth + 1, vertex); count++; seq[count][0] = Pair{depth, vertex}; } } } void init() { DFS(ROOT); for (int_t i = 1; (1 << i) <= count; i++) { for (int_t j = 1; j + (1 << i) - 1 <= count; j++) { seq[j][i] = std::min(seq[j][i - 1], seq[j + (1 << (i - 1))][i - 1]); } } } int_t depth(int_t x) { return seq[first[x]][0].depth; } int_t getLCA(int_t v1, int_t v2) { v1 = first[v1]; v2 = first[v2]; if (v1 > v2) std::swap(v1, v2); int_t length = log2(v2 - v1 + 1); return std::min(seq[v1][length], seq[v2 - (1 << length) + 1][length]).vertex; } } // namespace LCA //动态开点线段树的一个节点 struct Node { int_t begin; int_t end; int_t value; Node *left = nullptr; Node *right = nullptr; Node(int_t begin, int_t end) { this->begin = begin; this->end = end; value = 0; } int_t query(int_t pos) { int_t mid = (begin + end) / 2; if (begin == end && pos == mid) { return value; } if (pos <= mid) { if (left != nullptr) return left->query(pos); return 0; } else { if (right != nullptr) return right->query(pos); return 0; } } void add(int_t pos, int_t value) { int_t mid = (begin + end) / 2; if (begin == end && pos == mid) { this->value += value; return; } if (pos <= mid) { if (left == nullptr) { left = new Node(begin, mid); } left->add(pos, value); } else { if (right == nullptr) { right = new Node(mid + 1, end); } right->add(pos, value); } } }; //合并两棵动态开点线段树 Node *merge(Node *left, Node *right) { if (left == nullptr) return right; if (right == nullptr) return left; left->left = merge(left->left, right->left); left->right = merge(left->right, right->right); left->value += right->value; return left; } //表示一个玩家 struct Player { int_t from; int_t to; int_t lca; } players[LARGE + 1]; //表示一个节点上的上行和下行标记 struct Mark { //以这个点为起点的标记（上行标记） std::vector<int_t> up; //这个点为终点的询问标记（下行标记） std::vector<int_t> down; } marks[LARGE + 1]; //表示一个询问点的询问标记 struct Query { //这个点所询问的的上行标记 //即time(w)+dep(w) //会在这棵子树内查询满足dep(s)等于这个标记的节点数量 int_t up = 0; //这个点所询问的下行标记 //即time(w)-dep(w) //会在子树内查询满足dep(s)-2*dep(lca)等于这个标记的节点数量 int_t down = 0; } querys[LARGE + 1]; //到了某个点应该删除的标记 //到了这个点，在统计这棵子树的答案前，会先把这些标记删去 struct Remove { //要删掉的上行标记 std::vector<int_t> up; //要删掉的下行标记 std::vector<int_t> down; } removes[LARGE + 1]; //用于离散化 inline int_t rank(int_t x) { return std::lower_bound(numbers.begin(), numbers.end(), x) - numbers.begin() + 1; } inline void setRank(int_t &x) { x = rank(x); } pair_t DFS(int_t vertex, int_t *result, int_t from = 0) { Node *up = new Node(1, numbers.size()); Node *down = new Node(1, numbers.size()); for (int_t to : graph[vertex]) { if (to != from) { //首先递归查询子树答案 auto x = DFS(to, result, vertex); up = merge(up, x.first); down = merge(down, x.second); } } //打上当前节点的标记 { auto &mark = marks[vertex]; for (int_t x : mark.up) { up->add(x, 1); } for (int_t x : mark.down) { down->add(x, 1); } } //删除应该删除的标记 { auto &removing = removes[vertex]; for (int_t x : removing.up) { assert(up->query(x) >= 1); up->add(x, -1); } for (int_t x : removing.down) { assert(down->query(x) >= 1); down->add(x, -1); } } //统计当前节点的答案 result[vertex] = up->query(querys[vertex].up) + down->query(querys[vertex].down); return pair_t(up, down); } int main() { scanf("%d%d", &n, &m); for (int_t i = 1; i <= n - 1; i++) { int_t from, to; scanf("%d%d", &from, &to); graph[from].push_back(to); graph[to].push_back(from); } LCA::init(); for (int_t i = 1; i <= n; i++) { int_t time; scanf("%d", &time); auto &query = querys[i]; query.up = time + LCA::depth(i); query.down = time - LCA::depth(i); numbers.push_back(query.up); numbers.push_back(query.down); } for (int_t i = 1; i <= m; i++) { auto &player = players[i]; scanf("%d%d", &player.from, &player.to); player.lca = LCA::getLCA(player.from, player.to); //记录一下标记 marks[player.from].up.push_back(LCA::depth(player.from)); marks[player.to].down.push_back(LCA::depth(player.from) - 2 * LCA::depth(player.lca)); //记录一下删除标记 //之所以需要这个东西，是因为如果一个玩家的起点和中点都在一棵子树内，那么统计答案时可能会统计两遍 //把这个玩家的上行标记在起点和终点的LCA处删掉，而下行标记在LCA的父节点处删掉，以防止这个玩家恰好能被起点和终点的LCA统计到时被统计两遍 removes[player.lca].up.push_back(LCA::depth(player.from)); //把这个玩家的另一个标记在LCA的父节点处删掉 removes[LCA::parent[player.lca]].down.push_back(LCA::depth(player.from) - 2 * LCA::depth(player.lca)); numbers.push_back(LCA::depth(player.from)); numbers.push_back(LCA::depth(player.from) - 2 * LCA::depth(player.lca)); } //进行离散化 std::sort(numbers.begin(), numbers.end()); numbers.resize(std::unique(numbers.begin(), numbers.end()) - numbers.begin()); for (int_t i = 1; i <= n; i++) { { auto &query = querys[i]; setRank(query.up); setRank(query.down); } { auto &mark = marks[i]; std::for_each(mark.up.begin(), mark.up.end(), setRank); std::for_each(mark.down.begin(), mark.down.end(), setRank); } { auto &removing = removes[i]; std::for_each(removing.up.begin(), removing.up.end(), setRank); std::for_each(removing.down.begin(), removing.down.end(), setRank); } } static int_t result[LARGE + 1]; DFS(ROOT, result, 0); for (int_t i = 1; i <= n; i++) { cout << result[i] << " "; } return 0; } ```