tpd

<div class="post_brief"><p> 今天晚上的效率比白天高啊。</p>   树上莫队的另一道题。比糖果公园好写到哪里去了。   然后手写链表丑掉了导致调试半天+RE了一发。我还是太年轻了。   #include <cstdio> #include <cmath> #include <cstring> #include <algorithm> using namespace std; typedef struct node { int t; node *next; } edge; const int maxn = 50009; const int maxm = 100009; const int maxl = 17; node nlst[maxn], *np(nlst); struct chain { int sz; node *hd, *tl; chain() { hd = tl = 0; sz = 0; } inline void clear() { hd = tl = 0; sz = 0; } inline void push(int x) { np-> t = x; np-> next = 0; if (sz) { tl-> next = np; tl = np; } else { hd = np; tl = np; } ++ np; ++ sz; } inline void merge(chain a) { if (a....

<div class="post_brief"><p> 盯idy发现的题，之前想学然后放弃了，于是今天几乎写了一天。有种紧迫感啊。然后发现好多认识的人都是最近过的。</p>   思路比较简单，树上莫队。因为要修改，所以要把块的大小变成n2/3，然后用1086的方法分块。好像也可以直接按dfs序分块。两个端点和时间为三个关键字跑莫队。复杂度可以感受一下反正我也不会证。   要注意千万要控制LCA的用量，必需只能是O(n)级别的。在爬树的时候必需O(1)。我就是在移动时间的时候不小心手贱每次用一遍LCA，然后去检查在移动端点花了好久的时间。   比较不开心的是发现mac没法改栈空间？有两个点始终暴栈。而且拿另一台电脑的openSUSE跑，结果发现它的cpu没有mac好，跑得还比mac快！我猜是操作系统在捣鬼。mac还是比较坑啊不开心。然后在bzoj上跑的时间几乎是本地的5倍也是比较厉害啊。   #include <cstdio> #include <cmath> #include <cstring> #include <algorithm> using namespace std; const int maxn = 100009; const int maxl = 19; typedef struct node { int t; node *next; } edge; node nlst[maxn], *np(nlst); struct chain { int sz; node *hd, *tl; chain() { hd = tl = 0; sz = 0; } inline void clear() { hd = tl = 0; sz = 0; } inline void push(int x) { np-> t = x; np-> next = 0; if (sz) { tl-> next = np; tl = np; } else { hd = np; tl = np; } ++ np; ++ sz; } inline void merge(chain a) { sz += a....