[Luogu 3258] JLOI2014 松鼠的新家

---

LCA + 樹上差分。

我呢，因?yàn)槭菢淦是蟮?LCA，預(yù)處理了 DFN（DFS 序），于是簡化成了序列差分。

qwq不講了不講了，貼代碼。

#include <algorithm> #include <cstdio> #include <cstring>#define nullptr NULLconst int MAXN = 300010; int n, a[MAXN]; namespace HLD {int qwq[MAXN]; class Graph{private: bool vis[MAXN]; int num; struct Node{int depth, size, father, son, top, DFN; }s[MAXN]; struct Edge{int to; Edge *next; Edge(int to, Edge* next): to(to), next(next){}~Edge(void){if(next!=nullptr)delete next; }}*head[MAXN]; void Modify(int l, int r, int k){qwq[s[l].DFN] += k; qwq[s[r].DFN + 1] -= k; }void Add(int x, int y){int a, b; while((a = s[x].top) ^ (b = s[y].top))if(s[a].depth > s[b].depth){Modify(a, x, 1); x = s[a].father; }else{Modify(b, y, 1); y = s[b].father; }if(s[x].depth < s[y].depth)Modify(x, y, 1); elseModify(y, x, 1); }public: Graph(int n): num(0){memset(vis, 0, sizeof vis); memset(s, 0, sizeof s); std :: fill(head + 1, head + n + 1, (Edge*)nullptr); }~Graph(void){for(int i = 1; i <= n; ++i)delete head[i]; }void AddEdges(int u, int v){head[u] = new Edge(v, head[u]); head[v] = new Edge(u, head[v]); }void DFS1(int u, int k){s[u].depth = k; s[u].size = 1; int v; for(Edge* i = head[u]; i != nullptr; i = i -> next)if(!s[v = i -> to].depth){DFS1(v, k + 1); s[v].father = u; s[u].size += s[v].size; if(s[v].size > s[s[u].son].size)s[u].son = v; }}void DFS2(int u, int top){s[u].top = top; s[u].DFN = ++num; vis[u] = true; if(s[u].son)DFS2(s[u].son, top); int v; for(Edge* i = head[u]; i != nullptr; i = i -> next)if(!vis[v = i -> to])DFS2(v, v); }void Walk(int x, int y){Add(x, y); Modify(y, y, -1); }void Find(void){for(int i = 1; i < n; ++i)qwq[i + 1] += qwq[i]; for(int i = 1; i <= n; ++i)printf("%d\n", qwq[s[i].DFN]); }}*G; void Init(void){G = new Graph(n); for(int i = 1, u, v; i < n; ++i){scanf("%d %d", &u, &v); G -> AddEdges(u, v); }G -> DFS1(1, 1); G -> DFS2(1, 1); } }int main(void) {scanf("%d", &n); for(int i = 1; i <= n; ++i)scanf("%d", &a[i]); HLD :: Init(); for(int i = 1; i < n; ++i)HLD :: G -> Walk(a[i], a[i + 1]); HLD :: G -> Find(); return 0; }

---

謝謝閱讀。

轉(zhuǎn)載于:https://www.cnblogs.com/Capella/p/9884917.html

總結(jié)

以上是生活随笔為你收集整理的[Luogu 3258] JLOI2014 松鼠的新家的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。