老年退役选手体验NOIP2018被题目吊打……

NOIP2018铺设道路

题目大意: 给定长为$n$数列$a[i]$，每次操作可以任选$L,R$，令$a[i] -= 1$，其中$i \in [L,R]$。求最少操作次数使$a[i]$全都变为0。$1 \le n \le 10^5$。

去年NOIP前后就听说有道和NOIP2013积木大赛一模一样的题。

总之就是可以把操作反过来看成是将一个全0数列区间加1变成$a[i]$，然后区间加显然每次范围越大越好，那么每次区间加左端点一定尽可能靠左，所以只需要求有多少个块左边没有别的块即可。不难得出这个数目就是$\sum\max(a[i]-a[i-1],0)$。复杂度$O(n)$。

#include <bits/stdc++.h>
using namespace std;

#define rint register int
inline int rf(){int r;int s=0,c;for(;!isdigit(c=getchar());s=c);for(r=c^48;isdigit(c=getchar());(r*=10)+=c^48);return s^45?r:-r;}
int n, a, b, s; int main(){for(n = rf(); n--; b = rf(), s += max(b-a,0), a = b); return !printf("%d\n",s);}

NOIP2018货币系统

题目大意: 给定大小为$n$集合$a[i]$，求一个最小的集合$b[i]$，满足集合$\lbrace \sum x_ia[i] | x_1,x_2,…,x_n \in \mathbb N \rbrace = \lbrace \sum x_ib[i] | x_1,x_2,…,x_m \in \mathbb N \rbrace$。输出集合$b$的大小即可。$T \le 20$组数据，每组数据$n \le 100$，$1 \le a[i] \le 2.5 \times 10^4$。

数据范围限制比较诡异，似乎在暗示什么$O(Tnm)$或者$O(T(n^2+m))$类似的做法。直接按照要求模拟: 通过递推求出目标集合$\lbrace \sum x_ia[i] | x_1,x_2,…,x_n \in \mathbb N \rbrace$然后贪心反推出$b[i]$，即从小到大扫描目标集合，如果某个位置不能被表示，就加入$b$集合中，然后更新更大的数能否被表示。这样就得到了一个$O(T(nm+m^2))$，其中通过$a[i]$构造目标集合是$O(nm)$的，而从目标集合构造$b[i]$看上去是$O(m^2)$的。

实际上，仔细观察对于目标集合构造$b[i]$过程的两层循环:

for(rint i = 1, j; i <= m; i++) if(d[i]&&!f[i]) for(++s, j = i; j <= m; f[j] |= f[j-i], j++);

内层循环发生一次，则++s，但是s就是$b$集合的大小。显然有$|b| \le |a| = n$，因此这个二层循环均摊复杂度是不会超过$O(nm)$的。

因此写个暴力交上去就可以过。复杂度$O(Tnm)$，本人为方便剪枝排了一下序，复杂度$O(Tn(m + \log n))$。

#include <bits/stdc++.h>
using namespace std;

#define rint register int
inline int rf(){int r;int s=0,c;for(;!isdigit(c=getchar());s=c);for(r=c^48;isdigit(c=getchar());(r*=10)+=c^48);return s^45?r:-r;}
bool d[25005], f[25005]; int T, n, m, s, a[105];
int main()
{
    for(f[0] = d[0] = 1, T = rf(); T--; printf("%d\n",s))
    {
        n = rf(); generate(a+1,a+n+1,rf); sort(a+1,a+n+1); memset(d+1,0,m=a[n]); memset(f+1,0,m); s = 0;
        for(rint i = 1, j; i <= m; i++) for(j = 1; j <= n && a[j] <= i; d[i] |= d[i-a[j]], j++);
        for(rint i = 1, j; i <= m; i++) if(d[i]&&!f[i]) for(++s, j = i; j <= m; f[j] |= f[j-i], j++);
    }   return 0;
}

NOIP2018赛道修建

题目大意: 给定一棵$n$个点的边带权树，求在其上选择至少$m$条不重边的链，最短链最长是多少。$m \lt n \le 5 \times 10^4$。

首先把题目的恰好$m$拓展成至少$m$，对答案没有什么影响，因为条数更多显然不优，但考虑起来会容易一些。

刚开始想了一会儿没啥思路，重新读了一遍题，看到那个”最短赛道的长度尽可能大”的时候突然激起了OI选手的原始冲动，找回了当年的感觉……

所以肯定是二分答案了，那么就是要求最多可以拼出多少条长度不小于$mid$的链。树形DP每个点开一个vector或multiset贪心搞一搞就行了: 因为每个点只能向上传一个链，那么每个点处一定贪心匹配，然后将剩下的最长链传上去。这里的贪心匹配就是指对于所有儿子传上来的链，已经足够长的直接单独成链，不够长的找一个最短的加起来足够长的匹配。复杂度$O(n \log n \log w)$。二分边界可以做一点小剪枝。

#include <bits/stdc++.h>
using namespace std;
#define MAXN 50000
#define rint register int
inline int rf(){int r;int s=0,c;for(;!isdigit(c=getchar());s=c);for(r=c^48;isdigit(c=getchar());(r*=10)+=c^48);return s^45?r:-r;}
int fir[MAXN+5], f[MAXN+5], tot, n, m, s, lef, mid, rig, Ans; multiset<int>::iterator it; multiset<int> S;
struct Edge{int to,nex,w; Edge(){} Edge(int _to, int _nex, int _w){to=_to,nex=_nex,w=_w;}}e[(MAXN<<1)+5];
inline void Add(int a, int b, int w){e[tot] = Edge(b,fir[a],w), fir[a] = tot++, e[tot] = Edge(a,fir[b],w), fir[b] = tot++;}
void DP(int p, int fa)
{
    for(int u = fir[p], v; ~u; (v=e[u].to)^fa?DP(v,p),0:0, u = e[u].nex); S.clear(); f[p] = 0;
    for(int u = fir[p], v; ~u; (v=e[u].to)^fa?e[u].w+f[v]<mid?S.insert(e[u].w+f[v]),0:++s:0, u = e[u].nex);
    for(int a; S.size(); a = *S.begin(), S.erase(S.begin()), (it=S.lower_bound(mid-a))!=S.end()?S.erase(it),++s:f[p]=max(f[p],a));
}
int main()
{
    n = rf(); m = rf(); memset(fir+1,-1,n<<2); for(rint i = 1, u, v, w; i < n; u = rf(), v = rf(), Add(u,v,w=rf()), rig += w, i++);
    for(lef = 1, rig /= m; lef <= rig; mid = lef+rig>>1, s = 0, DP(1,0), s >= m ? Ans = mid, lef = mid+1 : rig = mid-1); return !printf("%d\n",Ans);
}

果然是老了啊……这道题交上去居然WA了。

注意一个细节: 一定要提前删去本来就足够长的，不能偷懒，以防后面一个本来就足够长的链因为被搜索到而和别人匹配，这不会立即影响匹配数，但是会影响上传值。例如有两个子树3和10，$mid = 10$，这时10必须单独成链，然后上传3；而如果13成链却只能上传0，所以不能认为13还是10成链对答案没有影响。

出于同样的原因，这里一定是从最小值开始找一个最小的能和它匹配的，而不是从最大值开始找一个最小的能和它匹配的，例如三个子树4 5 6，$mid = 9$，如果从最小值开始则9成链，上传6，从最大值开始虽然10也能成链，但只能上传5了。

顺带复习一下二分查找和邻接表……

NOIP2018旅行

题目大意: 给定一棵$n$点树或环套树，求一个字典序最小的DFS序。$n \le 5 \times 10^3$。

刚读完题，没看$m$的条件，感觉没思路。乍一看上去和Codeforces1106D挺像的，但是很快就可以意识到，那道题可以随便回溯，这道题只能回溯一次。

发现只有树或者环套树以后就可以做了，但是$O(n)$做法实现起来应该会挺麻烦的，又纠结了一段时间最后发现$n \le 5 \times 10^3$……

感觉自己不是很擅长这类环套树题目，找环后进行环上处理的过程总是感觉很痛苦……还好这道题$O(n^2 \log n)$可以过: 枚举环套树环上一条边删去跑最小字典序DFS。

于是也没有管常数，实现方式比较取巧: 因为懒得去找环了，所以枚举删所有边，如果删完以后还有环，在DFS的时候会死循环，当检测到循环(同一个点经过两次)的时候，就把当前序列的首项改为正无穷直接退出，字典序就是正无穷了，绝对不会被选上。

而且……最小字典序DFS空间复杂度怎么控制空间啊？搞得我只能开vector<int> q[5005]了……感觉这题写得又丑又慢又难受……起码代码不压行最短榜排到第二了。

#include <bits/stdc++.h>
using namespace std;
#define rint register int
inline int rf(){int r;int s=0,c;for(;!isdigit(c=getchar());s=c);for(r=c^48;isdigit(c=getchar());(r*=10)+=c^48);return s^45?r:-r;}
int fir[5005], n, m, tot, ban = -1; vector<int> S, T, q[5005]; bool b[5005];
struct Edge{int to,nex; Edge(){} Edge(int _to, int _nex){to=_to,nex=_nex;}}e[10005];
inline void Add(int a, int b){e[tot] = Edge(b,fir[a]), fir[a] = tot++, e[tot] = Edge(a,fir[b]), fir[b] = tot++;}
inline void Cmin(){for(rint i = 0; i < n; i++) if(S[i]<T[i]){T = S; return;} else if(S[i]>T[i]) return;}
void DFS(int p, int fa)
{
    q[p].clear(); S.push_back(p); if(b[p]){S.resize(n), S[0] = n+1; return;} b[p] = 1;
    for(int u = fir[p], v; ~u; (unsigned)(u^ban)>1&&(v=e[u].to)^fa?q[p].push_back(v),0:0, u = e[u].nex);
    sort(q[p].begin(),q[p].end()); for(auto v:q[p]) DFS(v,p); q[p].clear();
}
void Work(){S.clear(); memset(b+1,0,n); DFS(1,0); Cmin();}
int main()
{
    n = rf(); m = rf(); memset(fir+1,-1,n<<2); for(rint i = 1; i <= m; Add(rf(),rf()), i++); for(rint i = 0; i < n; T.push_back(n-i), i++);
    if(m<n) Work(); else for(ban = 0; ban < tot; Work(), ban += 2); for(rint i = 0; i < n; printf("%d%c",T[i],"\n "[i<n-1]), i++); return 0;
}

事后补题:

整理一下思路: 首先将DFS序不完整，即最后一定要回溯到1，这对答案没有影响。然后任何一种方案就都可以分为6部分: 从1好到出发并经过一部分子树到达环上一点$x$，从$x$开始绕着环走并经过一部分子树到达$y$，掉头绕着走经过剩下的子树回到$x$，继续绕着走并经过一部分子树到达$y$前一个点，掉头绕着走经过剩下的子树回到$x$，从$x$回溯经过剩下的子树到1。

那么不在环上的部分就是直接套最小字典序DFS，在换上的时候就顺着环走，只需要求出掉头的点即可。

掉头是从第二部分到第三部分，所以掉头点就是”从$x$开始绕着环走并经过一部分子树”的下一个要访问的点标号大于”掉头绕着走经过剩下的子树”的下一个要访问的点的标号。

“从$x$开始绕着环走并经过一部分子树”每个点的流程是先访问这个点，然后从小到大访问这个点子树中所有标号小于下一个点的，不访问标号大于下一个点的，然后走向下一个点重复。

“掉头绕着走经过剩下的子树”每个点的流程是掉头回溯到一个点，从小到大访问这个点子树中所有未访问的点，然后继续回溯。

所以掉头的条件就是【环上下一个点】标号大于【环上上一个子树有剩余的点的最小直接儿子】标号。

一开始纠结了挺久，总觉得这样有问题: 不能很好处理$x$点，因为如果$x$点的子树中有一个包含1，这个子树已经访问过了，会有问题。不过后来意识到没有影响。因为从1走上来以后一定第一个走$x$，然后走$x$的一部分子树，然后走$x$环上邻居中标号较小的那个。因此从一开始就走那个标号小的邻居，$x$点处是不可能掉头的。

看上去很复杂，模拟会很难受，不过学习别人/自己思考了一下实现的细节技巧，可以大大降低代码复杂度，感觉很巧妙:

• 代码第6行DFSc(p,fa)函数。

  对于带有顺序问题的环套树问题一般考虑用DFS找环。顺带复习一下Tarjan……

• 代码第5行vector<int> e[5005]。

  跑最小字典序DFS也只能vector<int> q[5005]了，但是可以不用邻接表而用vector存边，这样q和边表实际上是共用的，而且可以在DFS之前一劳永逸地排序。之前没有这样做是因为$O(n^2 \log n)$做法中需要枚举边，枚举边的时候邻接表显然比vector方便得多。

• 代码第5行DFSa(p)函数。

  事实上不需要真的比较字典序，最小字典序DFS在边表排过序以后可以大胆直接输出。注意这里采用bool b[5005]而不是记录上一个点，是为后面方便做准备，而且空间上直接重复利用找环过程中用到的标记数组。

• 代码第11行。

  就是处理环上选择方向的问题。c[0] = c[k]; c[k+1] = c[1];两句为后面方便做准备。

• 代码第12 ~ 16行。

  直接按照6各部分模拟看上去很麻烦，事实上只需要找到要掉头的边，将那条边删除然后直接套最小字典序DFS。即将所有问题都转化回最小字典序DFS——一个已经被很好解决了的问题。删边实际上也只需要删掉一条单向边就足够了，节省重复编码，不过正因为如此前面需要用bool b[5005]。

现在代码就又短又快了……

#include <bits/stdc++.h>
using namespace std;
#define rint register int
inline int rf(){int r;int s=0,c;for(;!isdigit(c=getchar());s=c);for(r=c^48;isdigit(c=getchar());(r*=10)+=c^48);return s^45?r:-r;}
vector<int> e[5005]; bool b[5005]; int s[5005], c[5005], n, m, t, k; void DFSa(int p){printf("%d ",p); b[p] = 1; for(auto v:e[p]) if(!b[v]) DFSa(v);}
bool DFSc(int p, int fa){b[s[++t]=p] = 1; for(auto v:e[p]) if(v^fa){if(b[v]){for(; s[t]^v; c[++k] = s[t--]); c[++k] = s[t--]; return 1;} if(DFSc(v,p)) return 1;} return b[s[t--]]=0;}
int main()
{
    n = rf(); m = rf(); for(rint i = 1, u, v; i <= m; u = rf(), v = rf(), e[u].push_back(v), e[v].push_back(u), i++);
    for(rint i = 1; i <= n; sort(e[i].begin(),e[i].end()), i++); if(m<n){return DFSa(1),puts(""),0;} DFSc(1,0);
    c[1]<c[k-1]?rotate(c+1,c+k,c+k+1):reverse(c+1,c+k+1); c[0] = c[k]; c[k+1] = c[1];
    for(rint i = 2, r = c[0], j; i <= k; i++)
    {
        j = n+1; for(auto v:e[c[i]]) v^c[i-1]&&v>c[i+1]?j=min(j,v):0; j<n+1?r=j:0;
        if(r < c[i+1] || i == k){e[c[i]].erase(lower_bound(e[c[i]].begin(),e[c[i]].end(),c[i+1])); break;}
    }   return memset(b+1,0,n),DFSa(1),puts(""),0;
}

NOIP2018填数游戏

题目大意: 给定一个$n \times m$的表格，求有多少种每个格子填充$0$或$1$的方法，使得从$(1,1)$到$(n,m)$的单调非上升路径满足: 靠下的路径形成的01序列字典序不小于靠上的路径形成的01序列字典序。其中”靠下”定义为两条路径第一个不同的分叉点处向下走的路径，”靠上”同理定义为向右走的路径。$1 \le n \le 8, m \le 10^6$。

提前知道了这道题是个规律题，感觉失去了很多乐趣……不过即使是这样，想要真正做出这道题而不是打表找规律(真香警告)个人感觉依然是比较有挑战的。为方便起见交换$n$和$m$，设$1 \le m \le 8$，$m \lt n \le 10^6$。记$Ans_m(n)$为一个$m$行$n$列的格子的答案。

$Ans_1(n) = 2^n$，单独试试就好了。

首先，手玩不难发现第一行总是随便填的，接着会发现每个1左下角就被强制填1了。

仔细思考不难发现，任何一个1，左下角一定全是1。进而得到:

Claim #1: 同一条对角线上，一定左下角全是1，右上角全是0，不能交替出现。

接下来沿着对角线分析，为方便起见对格子进行斜切:

这样每一步都必须向右，只能选择平走或向右下走。那么条件就变成了，对于任意一个竖列，一定上半部分是0，下半部分是1。那么横着看就相当于一个枚举子集。即对于中间的$n-m$行:

上面每一行是下一行的子集。这个问题是很好计数的: n个元素的集合$(的子集)^k$有多少种？答案是$(k+1)^n$。因为这等价于给每个元素表一个序号$i \in \lbrace 0,1,2,…,k\rbrace$表示其在前$i$次取子集的时候都被取到了，第$i+1$次却没被取到。

然后手动枚举两端的情况就得到$Ans_2(n) = 2 \times 3^{n-1} \times 2 = 4 \times 3^{n-1}$，以此类推。

真简单

然而并不是，在$m = 3$的时候这里就开始不一样了。事实上，【任意一个竖列，一定上半部分是0，下半部分是1】只是一个必要条件，而不是一个充分条件。还有什么情况呢？观察之前举得那个例子，就不是一个合法方案:

这是因为竖直有连续2个0出现，那么就会出现一条路径在其左侧分叉，在其右侧汇合，这样两条路径上的01序列完全相同，但是路径上下关系已经确定了，这样后面只要再出现分叉就会有问题。也就是说一旦出现这样一个”平行四边形”结构，那么后面的路径必须完全一样了，因此得到:

Claim #2: 任意竖列上出现连续两个0或1，其后的一个范围内所填的0或1必须相同。具体见下图，同色区域0或1必须相同。

不难发现，这样的结构在第二列就可以出现，于是我们试对于$m = 3$的情况讨论第二列填的是00、01还是11，就可以求得$Ans_3(n)$。

• 如果第二列填的是00或11，那么如图:

  

  最开始两列只能都填0或1，有4种方法；第三列随便填，有4种方法；此后的$n-3$列就是枚举子集(这时候即使再产生平行四边形结构也对填数方案没有影响了)，最后两列有4种方法。方法数就是$64 \times 3^{n-3}$。

• 如果第二列填的是01，那么没有产生平行四边形结构，从第三列开始，如图:

  

  这是候只有011可以不产生平行四边形结构了(011产生的平行四边形结构在最后一行，对答案没有影响)。那么枚举在第$i \in \lbrace m,m+1,…,n \rbrace$列填入了不是011的东西(即000,001和111三种)。方案数就是:

  $$2 \times \left( \left( \sum_{i=3}^{n-1} \underbrace{3}_{i} \times \underbrace{4}_{i+1} \times 3^{n-i-1} \times \underbrace{2}_{n+m-1} \right) + \underbrace{3 \times 3}_{i=n} + \underbrace{1 \times 3}_{\nexists i} \right) \times 2$$

  化简得原式$ = 16 \times 3^{n-2} - 12 + 12 = 16 \times 3^{n-2}$。

所以总方案数就是$Ans_3(n) = 64 \times 3^{n-3} + 16 \times 3^{n-2} = 112 \times 3^{n-3}$。

当$m \ge 4$的时候，不难发现第三列已经成为了限制因素，因为第三列总是要产生一个平行四边形结构的。

• 如果第二列填的是00或11，那么同上分析可以得:

  

  有$2 \times 2 \times 4^{m-2} \times 3^{n-m} \times 2^{m-1} = 2^{3m-3} \times 3^{n-m}$。

• 如果第二列填的是01，第三列填的是000或111，可得:

  

  有$2 \times 1 \times 2 \times 5 \times 4^{m-4} \times 3^{n-m} \times 2^{m-1} = 5 \times 2^{3m-7} \times 3^{n-m}$。

接下来情况就复杂了起来，因为接下来的情况产生平行四边形就不能忽略不计了，观察发现:

右半部分几乎完全相同，且最左上角第一个随便填，那么$3^{n-m-1} \times 2^{m}$的系数就几乎完全相同。除了右下角和左下方倒数第二个这种情况会有问题，但是正如我们在算$m = 3$遇到的问题是同样的，要么一直保持同一个方式填充，要么一旦违反这个模式，就会立即进入其他6中情况，枚举违反的位置，可以得到一个以4为公比的等比数列，等比数列求和后会发现$4^k$转化为$2^{2k}$后依然是$2^m$的倍数。极度不严谨的证明。

因此只需要搞清楚左半部分的方案数即可……打表吧，求了一天没通过严谨可证的方法求出来，果然是老年选手。

提出$3^{n-m-1} \times 2^{m}$的系数，对左半边一个直角梯形打表(直角梯形等价于平行四边形割掉右半部分，而右半部分根据如上分析一定至少是$2^{m-2}$，那么直接用$m \times (m+1)$平行四边形(即答案)逆推出直角梯形即可):

#include <bits/stdc++.h>
using namespace std;
#define MOD 1000000007
#define rint register int
inline int rf(){int r;int s=0,c;for(;!isdigit(c=getchar());s=c);for(r=c^48;isdigit(c=getchar());(r*=10)+=c^48);return s^45?r:-r;}
inline int fxp(int s, int n=MOD-2){int a=1;for(;n;n&1?a=1ll*a*s%MOD:0,s=1ll*s*s%MOD,n>>=1);return a;}
int f[9] = {0,1,3,14,57,223,887,3543,14167};
int g[9] = {0,2,9,42,168,666,2658,10626,42498};
int Work(int n, int m){switch(n<m?n^=m^=n^=m:0,m)
{
    case 1 : return fxp(2,n);
    case 2 : return 4ll*fxp(3,n-1)%MOD;
    case 3 : return 112ll*fxp(3,n-3)%MOD;
    default: return (n>m?1ll*g[m]*fxp(3,n-m-1)%MOD:1ll*f[m])*fxp(2,m)%MOD;
}}  int main(){return!printf("%d\n",Work(rf(),rf()));}

浪费了一整天的大好时光。

事后咕题:

发现居然有人推出来了？不过依然不是手算的，是用递推求的。感兴趣的可以戳这里(或者直接去百度)。

坐等谁能手算到$8 \times 8$一定要告诉我！！！！！！

NOIP2018保卫王国

题目大意: 给定一棵$n$个点的树，每个点涂黑或白，黑色有代价，每条边必须有一个黑点，给定$m$个询问每次固定两个点的颜色，求染色方案的最小代价。$n,m \le 10^5$。

终于可以写一道正经的码代码题目了。

这东西我记得当时叫做”链分治”，不过后来好像还是普遍接受了”动态DP”这样一个名字。

链分治的主体思路就是将DP运算看做矩阵运算(重载乘法和加法)，然后用树链剖分维护树上矩阵。具体过程就是将一个点的所有轻儿子”浓缩”(这个过程一般具有可减性)到这个点上，对于每条树链做一个链式的DP，即树链上一个点的答案就是链的前缀和。修改的时候修改轻儿子的”浓缩”值即可。

以这道题为例，展示一下链分治的通用思考过程。

首先有DP方程(0表示不放军队，即白色；1反之):

$$f[p][0] = \sum f[v][1] \\ f[p][1] = w_p + \sum \min(f[v][0],f[v][1]) \\$$

第二步考虑”浓缩”轻儿子，记录一个轻儿子的贡献和:

$$g[p][0] = \sum_{v \ne hvy_p} f[v][1] \\ g[p][1] = w_p + \sum_{v \ne hvy_p} \min(f[v][0],f[v][1]) \\$$

那么用”浓缩”后的值来维护DP值就有:

$$f[p][0] = g[p][0] + f[hvy_p][1] \\ f[p][1] = g[p][1] + \min(f[hvy_p][0],f[hvy_p][1])$$

第三步将DP方程改为矩阵乘法，这里定义取min是矩阵加法，相加是矩阵乘法。

$$\left[ \begin{matrix} +\infty & g[p][0] \\ g[p][1] & g[p][1] \\ \end{matrix} \right] \left[ \begin{matrix} f[hvy_p][0] \\ f[hvy_p][1] \\ \end{matrix} \right] = \left[ \begin{matrix} f[p][0] \\ f[p][1] \\ \end{matrix} \right]$$

然后注意一下边界情况: 现在的单位矩阵是$\left[\begin{matrix}0 & +\infty \ +\infty & 0 \end{matrix}\right]$，而最后的答案就是:

$$\left(\prod_p\left[ \begin{matrix} +\infty & g[p][0] \\ g[p][1] & g[p][1] \\ \end{matrix} \right]\right) \left[ \begin{matrix} 0 \\ 0 \\ \end{matrix} \right]$$

得到$f[1][0/1]$，而最后答案又是两者取min。这里有一个小Trick，观察发现:

$$\left[ \begin{matrix} +\infty & g[a][0] \\ g[a][1] & g[a][1] \\ \end{matrix} \right] \left[ \begin{matrix} +\infty & g[b][0] \\ g[b][1] & g[b][1] \\ \end{matrix} \right] = A$$

展开以后一定是$A[0][1] \gt A[0][0]$且$A[1][1] \gt A[1][0]$，因此最后答案就是min(A[0][1],A[1][1])，可以简化代码。

具体的修改过程需要缜密划分，不要漏掉情况，详见代码中void UP(p)函数。

复杂度$O(n \log n + m \log ^2 n)$。在UOJ上会被Hack数据卡常/卡复杂度成97……这题应该$O((n + m) \log n)$才是intended算法，那就先咕了再说。

#include <bits/stdc++.h>
using namespace std;
#define MAXN 100000
#define ll long long
#define lc(p) (p<<1)
#define rc(p) (p<<1|1)
#define mid ((lef+rig)>>1)
#define INF 100000000000ll
#define rint register int
inline int rf(){int r;int s=0,c;for(;!isdigit(c=getchar());s=c);for(r=c^48;isdigit(c=getchar());(r*=10)+=c^48);return s^45?r:-r;}
vector<int> e[MAXN+5]; ll f[MAXN+5][2], g[MAXN+5][2], T1, T2, A; int w[MAXN+5], fa[MAXN+5], dep[MAXN+5], sz[MAXN+5], hvy[MAXN+5], pos[MAXN+5], top[MAXN+5], bot[MAXN+5], s[MAXN+5], n, m, d;
struct Mat{ll c[2][2]; inline Mat(){c[0][0]=c[0][1]=c[1][0]=c[1][1]=INF;} inline Mat(ll A, ll B, ll C, ll D){c[0][0]=A,c[0][1]=B,c[1][0]=C,c[1][1]=D;}}I(0,INF,INF,0),C,T,t[262145];
inline Mat &operator * (const Mat &A, const Mat &B)
{ 
    C.c[0][0]=min(A.c[0][0]+B.c[0][0],A.c[0][1]+B.c[1][0]);C.c[0][1]=min(A.c[0][0]+B.c[0][1],A.c[0][1]+B.c[1][1]);
    C.c[1][0]=min(A.c[1][0]+B.c[0][0],A.c[1][1]+B.c[1][0]);C.c[1][1]=min(A.c[1][0]+B.c[0][1],A.c[1][1]+B.c[1][1]); return C;
}
void DFS1(int p){dep[p]=dep[fa[p]]+1,sz[p]=1;for(auto v:e[p])v^fa[p]?fa[v]=p,DFS1(v),sz[p]+=sz[v],sz[v]>sz[hvy[p]]?hvy[p]=v:0:0;}
void DFS2(int p){s[pos[p]=++d]=bot[p]=p;hvy[p]?top[hvy[p]]=top[p],DFS2(hvy[p]),bot[p]=bot[hvy[p]]:0;for(auto v:e[p])v^fa[p]&&v^hvy[p]?top[v]=v,DFS2(v),0:0;}
void DP(int p){g[p][0]=0;g[p][1]=w[p];for(auto v:e[p])v^fa[p]?DP(v),v^hvy[p]?g[p][0]+=f[v][1],g[p][1]+=min(f[v][0],f[v][1]):0:0;f[p][0]=g[p][0]+f[hvy[p]][1];f[p][1]=g[p][1]+min(f[hvy[p]][1],f[hvy[p]][0]);}
void BD(int p, int lef, int rig){t[p]=lef^rig?BD(lc(p),lef,mid),BD(rc(p),mid+1,rig),t[lc(p)]*t[rc(p)]:Mat(INF,g[s[lef]][0],g[s[lef]][1],g[s[lef]][1]);}
inline void ED(int p, int lef, int rig, int x){t[p]=lef^rig?x<=mid?ED(lc(p),lef,mid,x):ED(rc(p),mid+1,rig,x),t[lc(p)]*t[rc(p)]:Mat(INF,g[s[lef]][0],g[s[lef]][1],g[s[lef]][1]);}
inline Mat QU(int p, int lef, int rig, int L, int R){return L^lef||R^rig?(L<=mid?QU(lc(p),lef,mid,L,min(mid,R)):I)*(R>mid?QU(rc(p),mid+1,rig,max(mid+1,L),R):I):t[p];}
void UP(rint p)
{
    for(ED(1,1,n,pos[p]), p = top[p]; p^1; ED(1,1,n,pos[fa[p]]), p = top[fa[p]])
        T = QU(1,1,n,pos[p],pos[bot[p]]), g[fa[p]][0] -= f[p][1], g[fa[p]][1] -= min(f[p][0],f[p][1]),
        f[p][0] = T.c[0][1], f[p][1] = T.c[1][1], g[fa[p]][0] += f[p][1], g[fa[p]][1] += min(f[p][0],f[p][1]);
}
int main()
{
    n = rf(); m = rf(); rf(); generate(w+1,w+n+1,rf); for(rint i = 1, u, v; i < n; u = rf(), v = rf(), e[u].push_back(v), e[v].push_back(u), i++); DFS1(1); DFS2(top[1]=1); DP(1); BD(1,1,n);
    for(int a, x, b, y; m--; A = min(T.c[0][1],T.c[1][1]), printf("%lld\n",A<INF?A:-1), g[a][x] = T1, UP(a), g[b][y] = T2, UP(b))
        a = rf(), x = !rf(), b = rf(), y = !rf(), T1 = g[a][x], T2 = g[b][y], g[a][x] = INF, UP(a), g[b][y] = INF, UP(b), T = QU(1,1,n,pos[1],pos[bot[1]]); return 0;
}

注意一下调了巨长时间: g[a][x] = INF, UP(a), g[b][y] = INF, UP(b)一开始我偷懒写成了g[a][x] = g[b][y] = INF, UP(a), UP(b)。这样是不行的，加入a是b的祖先，那么更新a的时候就要用到b的数据，这时候b的数据是错的。

而且早些时候我还试图偷懒写成了swap(T1,g[a][x]), swap(T2,g[b][y])，其中T1和T2都是$+\infty$，准备操作完再swap回来。由于同样的原因，如果a是b的祖先，实际上最后g[a][x]还真的不一定就是$+\infty$。

完了要是考NOIP2018怕不是要D2退役了……

---

P.S.: NOIP2018发生了啥啊？这UOJ口碑有点惨惨啊？

扫描二维码即可在手机上查看这篇文章，或者转发二维码来分享这篇文章: