NOIP2018做题题解

老年退役选手体验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)$。

1
2
3
4
5
6
#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]$过程的两层循环:

1
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))$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#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每个点开一个vectormultiset贪心搞一搞就行了: 因为每个点只能向上传一个链,那么每个点处一定贪心匹配,然后将剩下的最长链传上去。这里的贪心匹配就是指对于所有儿子传上来的链,已经足够长的直接单独成链,不够长的找一个最短的加起来足够长的匹配。复杂度$O(n \log n \log w)$。二分边界可以做一点小剪枝。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#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]了……感觉这题写得又丑又慢又难受……起码代码不压行最短榜排到第二了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#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]

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#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三种)。方案数就是:

    化简得原式$ = 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)$平行四边形(即答案)逆推出直角梯形即可):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#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反之):

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

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

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

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

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

展开以后一定是$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算法,那就先咕了再说

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#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)。这样是不行的,加入ab的祖先,那么更新a的时候就要用到b的数据,这时候b的数据是错的。

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

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



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


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


文章作者: Magolor
文章链接: https://magolor.cn/2019/06/12/2019-06-12-blog-01/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Magolor
扫描二维码在手机上查看或转发二维码以分享Magolor的博客