NOIp 2018

普及 + 省选 = 提高

Posted by Ghastlcon on November 11, 2018
CC 采用 $\text{CC BY-NC-SA 4.0}$ 许可,转载请注明:“转自 NOIp 2018

$\text{NOIp }2018$

这些日子很快就过去了呢,又是 $\text{NOIp 2018}$ 了。

今年可是原题大战和普及省选题呢。

总算把时间安排好了。

想看 $\text{Solution}$ 的直接翻 $\text{Catalog}$ 。

$\text{Day }[-??,\, -2)$

不断的胡策,$\text{LGJ}$ 居然连题都不看。

就在停课中天天循环。

$\text{Day }-2$

数据非常严谨

$\text{P1}$ 被最短路水过,$\text{P2}$ 被假分治 $\mathrm O(NM\cdot \min(N,\,M))$ 水到 $90\%$ 。

$\text{Day }-1$

$\text{LGJ}$ 断网测,没有什么好说的。

$\text{Day }0$

$\text{LGJ}$ 断网测,然后我连挂 $2$ 题。

已经没有什么好害怕的了。

诡异的分房表,不知道是按照什么诡异顺序来的。

居然和退役狗分在同房。

跟去年去相同的地方吃饭,相同的位置,居然还是相同的座位安排。

可惜 $\text{aspe}$ 已经不在了。

这 $\text{KsCla}$ 的顾忌也太多了吧。

$\text{Day }1$

发现自己书包里面的笔漏水了,还好没弄脏准考证,RP -= oo ……

密码:[email protected]$Tian! 现场并没有意识到是什么。

$\text{i7-8700K}$!$32\texttt{GB}$!真是太令人感动了。

看完 $\text{P1}$ 之后感觉这不是 $\text{NOIp 2013}$ 原题吗?然后“首尾相连”让我感觉很奇怪,难道不应该是环?

链的做法差分之后就做完了,然后直接过了大样例?

这大样例莫不是数据湿度很高?本来不应该是环吗,怎么会直接过了大样例?并且怎么可能出原题呢?

然后我过了好久才理解到“首尾相连”的意义是第 $i$ 块地的尾和第 $i+1$ 块地的首相连……

我居然写出了 $\text{Day1 P1}$!太令人感动了。


我们先猜想 $B\subseteq A$!数学归纳法证明简单。

那么显然 $A$ 内的能被其他元素表示出来的元素就是不必要的?就这样做完了?

然后我写了个 $\mathrm O(NM^2)$ 多重背包发现不会优化……

过了会才发现这是个完全背包……


这 $\text{P3}$ 显然可以 $2$ 分答案啊,然后就变成了找尽量多条长度不少于 $k$ 的不相交链。

这个怎么做呢?……考虑贪心?子树内的连成的链显然被父亲拆开不会更优,所以直接用平衡树维护?

每次从平衡树内取最大值,支持整个树加权合并?……直接上启发式合并!

好的 $\mathrm O(N\log^3 N)$ 做法到手。但我并没有注意到每次只会从平衡树内取最大值。

试了下 $5\cdot 10^4$,发现需要 $3\texttt s$ 。然后剩下的时间我就写了特判直径特判菊花特判链。

顺手还来了几把扫雷,但到最后都没有意识到并不需要合并。


感觉全世界都 $\text{AK}$ 了,也就只有我写了 $\log^3$ 做法。

甚至还有诡异的 $\text{DP}$ 做法和 $\mathrm O(N\log^{1.5}N)$ 做法。

没想到桂一真的没人管了呢,说不定以后就不搞了,这真是令人悲伤。

下午打则,但没人陪我,也就只能跟机器打打的样子。


晚上居然玩 $\text{quickdraw}$ 。

既然去年是 $\text M$,今年就 $\text K$ 吧!

持续无聊,甚至在继续玩 $\text{DL}$ 。

不过感觉普及组好难的样子?$\text{Manacher}$ 直接出来了?怕不是有毒。

$\text{Day }2$

睡过头了,早餐几片面包解决,RP -= oo ……

密码:%xiao#SHU!shen9XIA,不是改革开放差评。

怎么没看懂 $\text{P1}$ 的题意啊,这是要干嘛啊。

看样例和数据范围,发现 $n-1\leq m\leq n$?意思是这就是个树或环套树?

迅速写完 $m=n-1$ 的,发现有环的情况只要暴力枚举拆掉 $1$ 条边即可。

极限数据跑了 $1.2\texttt s$,改成邻接表就走了。


看了下时间,才 $09:10$,不虚不虚。

理解 $\text{P2}$ 题意又用了很久。大概是只要有着

就是非法的?

写了个暴力枚举判断,发现 $n=m=3$ 直接错了……

然后找到反例,发现根本不可能进行 $\text{DP}$,后效性是摆在那里的……还以为是个矩阵加速来的……

野心不要太大,收起你的狼子野心。——$\text{KsCla}$

写了 $65\%$ 就跑了,打表出规律真好玩。

此时大约 $10:00$,并没有在这个毒题上浪费太多时间。


$44\%$?写了写了!

链?分 $3$ 种情况写了写了!

深度不超过 $100$?……我会暴力更新 $\text{DP}$!?……

动态 $\text{DP}$?

并不想去写感觉细节巨多的标算。


我以为我 $\text{P2}$ 不会做已经凉了,没想到全世界都不会 $\text{P2}$ 。

似乎有好多人都没调出来 $\text{P2/P3}$?

如果不挂题的话就很好了呢。

$\text{Memories}$

至少没有像去年那样挂得严重。

$\text{P3}$ 的失误的确是不应该出现的。

但是无论如何,明天要滚回去文化课。

$3$ 周的停课,还有那依然不变的 $8$ 小时前离场的短暂 $1$ 刻。

感叹是下面几届的学生怎么待遇这么好,学校开放程度这么高,个个都跑来停课和报提高?

还有桂一不知道搞什么,以后要不搞了?这到底是什么奇怪的操作?

大概是时代变了吧。这届可能是正在处于这个分界点上的。从 $\text{SMOJ}$ 到自主招生重开到中考停课,无不都是在我们这里先做试验的。

$\text{OI}$ 之路现在已经能够看到尽头,前面的人的路已经不长了,自己的最后也不知道会如何。很多事情却并不是自己能够预测到的。

剩下最后 $1$ 年了。

$\text{Solution}$

$\text{P1}$

$60\%$

每次找到最长的不包含 $0$ 的段,直接 $-1$ 即可。

时间复杂度 $\mathrm O(N^2)$ 。

$100\%$

因为是区间加,所以我们先把原数组进行差分。

然后我们每次可以对某个数 $-1$,某个数 $+1$,最后使得整个数组变为 $0$ 。

显然整个差分数组的和不会为负数。因为我们可以不断地对差分数组第 $n+1$ 个数 $+1$,所以我们并不需要考虑差分数组中的负数。那么答案就是差分数组中所有正数的和。

时间复杂度 $\mathrm O(N)$ 。

#include <iostream>

#include <algorithm>

#include <cstdio>

#define N 100020

using namespace std;

int a[N];

int main(void) //road.cpp

{
    int n;
    int i, o;

    freopen("road.in" , "r", stdin );
    freopen("road.out", "w", stdout);

    scanf("%d", &n);
    for(i = 1, o = 0; i <= n; i ++)
    {
        scanf("%d", &a[i]);
        if(a[i] > a[i - 1])
            o += a[i] - a[i - 1];
    }
    printf("%d\n", o);

    return 0;
}

$\text{P2}$

$??\%$

这题的部分分应该怎么做?……

$100\%$

引理 $\text A$:最优解 $(m,B)$ 中,必有 $B\subseteq A$ 。

设 $a$ 为 $A$ 中的最小元素
则 $B$ 中不可能包含比 $a$ 小的元素,并且必须包含 $a$
反证,假设有 $k\in B,\,k\notin A$,根据要求 $B$ 不能表示出 $A$ 不能表示的元素
因为 $k\notin A$,所以 $k$ 必可以被 $A$ 表示出
那么选 $k$ 就是没有任何必要的($a$ 已被选,意味着后续的组合必然与 $A$ 表示出数相同,意味着就能表示出 $k$)

问题转变为 $A$ 中有多少个元素是不必要的:即能够被其它元素表示出。

完全背包,记 $f(i,\,j)$ 为前 $i$ 个元素能否表示出 $j$,则

边界为 $f(0,\,0)=1$ 。答案即为 $n-\sum_{i=0}^{n-1}f(i,\,a_{i+1})$ 。

时间复杂度 $\mathrm O(NV)$ 。

#include <iostream>

#include <algorithm>

#include <cstdio>

#define N 103

#define M 25003

using namespace std;

int a[N];
bool f[N][M];

int main(void) //money.cpp

{
    int t, n;
    int i, j, k;

    freopen("money.in" , "r", stdin );
    freopen("money.out", "w", stdout);

    scanf("%d", &t);
    while(t --)
    {
        scanf("%d", &n);
        for(i = 1; i <= n; i ++)
            scanf("%d", &a[i]);
        sort(a + 1, a + n + 1);

        f[0][0] = true;
        for(i = 1; i <= n; i ++)
            for(j = 0; j <= a[n]; j ++)
            {
                f[i][j] = f[i - 1][j];
                if(j >= a[i])
                    f[i][j] |= f[i][j - a[i]];
            }
        for(i = 1, k = n; i < n; i ++)
            k -= f[i][a[i + 1]];
        printf("%d\n", k);
    }

    return 0;
}

$\text{P3}$

$20\%$

$m=1$,即要求在树上找权值和最大的路径。

直接做树的直径即可。时间复杂度 $\mathrm O(N)$ 。

$100\%$

首先要求最大化 $m$ 条路径的最小值,这意味着可以先 $2$ 分答案 $k$,问题转变成找出尽量多条长度不小于 $k$ 的不相交链。

考虑某些叶子结点的共同父亲 $x$:如果只考虑 $x$ 的子树,显然可以用类似“田忌赛马”的思想:对于某个儿子 $s$,设边权为 $w$,那么应该找出 $\geq k-w$ 的,并且最小的另 $1$ 个儿子 $s’$ 匹配。

匹配完成之后呢?

引理 $\text A$:用上面的策略进行匹配之后,从 $x$ 的祖先再连下来 $1$ 条链从而拆散 $x$ 的 $1$ 对匹配是不优的。

“拆散”

在上面已经保证了尽量多的匹配
拆散之后减少了 $1$ 匹配,又增加了 $1$ 匹配
若被拆散后还能够继续匹配,则意味着未拆散之前还没有达到最大匹配,矛盾

因此我们只需要在 $x$ 应用“田忌赛马”策略得到最大匹配,然后将未匹配的,边权最大的结点传到父亲即可。注意只需要传 $1$ 个,因为最多只能再有 $1$ 条链连下来。

显然若全部儿子都匹配了,则传上 $0$ 即可(代表 $x$ 自己)

对于父亲,将传上来的所有儿子权值都加上边权,然后继续“田忌赛马”即可得到最优解。

时间复杂度 $\mathrm O(N\log N\log L)$ 。

#include <iostream>

#include <algorithm>

#include <cstdio>

#include <vector>

#include <utility>

#define N 50020

using namespace std;

int h[N], v[N << 1], w[N << 1], x[N << 1];
vector<pair<int, int> > d;
int f[N], o;

int Check(int p, int k)
{
    int i, j, o;

    for(i = d.size() - 1, j = o = 0; i > -1; i --)
    {
        if(i == p)
            continue;
        while(j < i && (d.at(i).first + d.at(j).first < k || j == p))
            j ++;
        if(j >= i)
            break;
        o ++;
        j ++;
    }

    return o;
}

void DFS(int x, int p, int k)
{
    int i, c;
    int l, m, r;

    f[x] = 0;
    for(i = h[x]; i; i = ::x[i])
        if(v[i] != p)
        {
            DFS(v[i], x, k);
            f[v[i]] += w[i];
        }

    d.clear();
    for(i = h[x]; i; i = ::x[i])
        if(v[i] != p)
        {
            c = f[v[i]];
            if(c >= k)
                o ++;
            else
                d.push_back(make_pair(c, v[i]));
        }
    sort(d.begin(), d.end());

    c = Check(d.size(), k);
    o += c;
    if((c << 1) < (signed)d.size())
    {
        for(l = 0, r = d.size(); l + 1 < r; )
            if(Check(m = (l + r) >> 1, k) == c)
                l = m;
            else
                r = m;
        f[x] = f[d.at(l).second];
    }

    return;
}

void AddEdge(int u, int v, int w)
{
    static int c = 0;

    x[++ c] = h[u];
    h[u] = c;
    ::v[c] = v;
    ::w[c] = w;

    return;
}

int main(void) //track.cpp

{
    int n, m, u, v, w;
    int i, l, r, k;

    freopen("track.in" , "r", stdin );
    freopen("track.out", "w", stdout);

    scanf("%d %d", &n, &m);
    for(i = 1, r = 0, l = N; i < n; i ++)
    {
        scanf("%d %d %d", &u, &v, &w);
        AddEdge(-- u, -- v, w);
        AddEdge(   v,    u, w);
        l = min(l, w);
        r += w;
    }

    for(r ++; l + 1 < r; )
    {
        k = (l + r) >> 1;
        o = 0;

        DFS(0, 0, k);
        if(o >= m)
            l = k;
        else
            r = k;
    }
    printf("%d\n", l);

    return 0;
}

$\text{P4}$

$60\%$

$m=n-1$,即给定的图是树。

实际上是要求最小化该树的前序遍历。

直接贪心地将每个结点的儿子从小到大排序,然后从结点 $0$ 开始(最小)遍历即可。

时间复杂度 $\mathrm O(N)$ 。

$100\%$

剩余的 $40\%$ 保证 $m=n$,即环套树。

由于不可能完整地走过这个环,并且要求经过所有结点,因此最优解上必定恰好不经过环的 $1$ 条边。

枚举这条边,将其置为不可通过,然后用类似树的做法。

时间复杂度 $\mathrm O(N^2)$ 。

#include <iostream>

#include <algorithm>

#include <cstdio>

#include <cstring>

#include <vector>

#include <utility>

#define N 5020

using namespace std;

vector<pair<int, int> > e[N];
int h[N], v[N << 1], w[N << 1], x[N << 1];
int k[N], c;
int o[N];
bool u[N];

void DFS(int x, int p, int g)
{
    int i;

    if(u[x])
        return;
    u[x] = true;

    k[c ++] = x;
    for(i = h[x]; i; i = ::x[i])
        if(v[i] != p && w[i] != g)
            DFS(v[i], x, g);

    return;
}

void AddEdge(int u, int v, int w)
{
    static int c = 0;

    x[++ c] = h[u];
    h[u] = c;
    ::v[c] = v;
    ::w[c] = w;

    return;
}

int main(void) //travel.cpp

{
    int n, m, u, v;
    int i, j;

    freopen("travel.in" , "r", stdin );
    freopen("travel.out", "w", stdout);

    scanf("%d %d", &n, &m);
    for(i = 0; i < m; i ++)
    {
        scanf("%d %d", &u, &v);
        e[-- u].push_back(make_pair(-- v, i));
        e[   v].push_back(make_pair(   u, i));
    }
    for(i = 0; i < n; i ++)
        sort(e[i].begin(), e[i].end());
    for(i = 0; i < n; i ++)
        for(j = e[i].size() - 1; j > -1; j --)
            AddEdge(i, e[i].at(j).first, e[i].at(j).second);

    if(m == n - 1)
    {
        DFS(0, 0, -1);
        for(i = 0; i < n; i ++)
        {
            if(i)
                putchar(' ');
            printf("%d", k[i] + 1);
        }
        printf("\n");
    }
    else
    {
        o[0] = n;
        for(i = 0; i < m; i ++)
        {
            c = 0;
            memset(::u, false, sizeof(::u));
            DFS(0, 0, i);
            if(c == n)
            {
                for(j = 0; j < n; j ++)
                    if(o[j] < k[j])
                        break;
                    else if(o[j] > k[j])
                    {
                        for(j = 0; j < n; j ++)
                            o[j] = k[j];
                        break;
                    }
            }
        }

        for(i = 0; i < n; i ++)
        {
            if(i)
                putchar(' ');
            printf("%d", o[i] + 1);
        }
        printf("\n");
    }

    return 0;
}

$\text{P5}$

$65\%$

通过打表得出 $n\leq 3$ 时的通项。

$100\%$

通过打表得出 $\require{enclose}\enclose{horizontalstrike}{n\leq 8}$ 时的通项。

实际上是有科学的做法的。

以下的“左下”,“右上”等方位词,均表示原矩阵中的某个 $2\times 2$ 的子矩阵。

  1. 合法矩阵中不能够包含“左下 $0$,右上 $1$”,即每条从左下到右上的对角线单调不递增;
    条件

  2. 合法矩阵中,若有着“左下和右上相等”的位置,则“右下到矩阵末的子矩阵左下到右上的所有对角线均相等”。
    条件

这两个条件分别代表着两方向相等与不等的情况,可以简单地严格证明以上两条是必要条件。

至于是充分条件,当然也可以严格证明。由于我个人认为感性理解比数学归纳证明好多了,因此不做论述。


以下只考虑 $3\leq n\leq m$ 的情况。对于 $n>m$ 的情况,可以交换 $n,\,m$ 而不改变答案;对于 $\min(n,\,m)<3$ 的情况,直接使用 $65\%$ 做法的通项计算。

我们考虑下面这条对角线。它必须满足条件 $1$ 与条件 $2$ 。

第 $3$ 条对角线

注意到这条对角线在满足条件 $1$ 的情况下,必然会触碰条件 $2$!

这意味着条件 $2$ 会限制相当大的子矩阵。

下面分情况考虑。

  1. $(0,\,1),\,(1,\,0)$ 相同
    如图
    这时候左上角的 $3$ 个格子共有 $4$ 种可能,有 $n-2$ 条拥有 $4$ 种可能的红色对角线,$m-n$ 条拥有 $3$ 种可能的绿色对角线,$n-1$ 条拥有 $2$ 种可能的橙色对角线,因此这种情况的贡献为 $4\cdot 4^{n-2}\cdot 3^{m-n}\cdot 2^{n-1}$;
  2. $(0,\,2),\,(1,\,1),\,(2,\,0)$ 相同,$(0,\,1),\,(1,\,0)$ 不同
    如图
    左上角的 $6$ 个格子仍然共有 $4$ 种可能,注意粉色对角线有 $5$ 种可能(棕色位置可以不相等),那么有 $n-4$ 条拥有 $4$ 种可能的红色对角线(图中没有),$m-n$ 条拥有 $3$ 种可能的绿色对角线,$n-1$ 条拥有 $2$ 种可能的橙色对角线,这种情况的贡献为 $4\cdot 5\cdot 4^{n-4}\cdot 3^{m-n}\cdot 2^{n-1}$;
  3. $(2,\,0),\,(1,\,1),$ 相同,$(0,\,1),\,(1,\,0)$ 不同,$(1,\,1),\,(0,\,2)$ 不同
    如图
    左上角的 $6$ 个格子只有 $2$ 种可能,但是注意上方没被限制的共有 $2$ 行,并且会出现这样子的情况
    新限制
    如果红色对角线被放了相同的数字,那么就会出现新的蓝色限制(延伸到矩阵末)。
    记 $f(i,\,j,\,k)$(其中 $j,\,k$ 均为 $0$ 或 $1$)为对于上面的 $2$ 行,决策了前 $i$ 列,$(1,\,i)$ 放的数字是 $j$,是否已经出现过新限制(也即是否会限制到第 $i$ 列)的方案数。具体转移看代码。
    另外最后仍然会有 $n-2$ 条拥有 $2$ 种可能的橙色对角线,因此这种情况的贡献为 $2\cdot 2^{n-2}\cdot (f(m,\,0,\,0)+f(m,\,0,\,1)+f(m,\,1,\,0)+f(m,\,1,\,1))$;
  4. $(0,\,2),\,(1,\,1),$ 相同,$(0,\,1),\,(1,\,0)$ 不同,$(1,\,1),\,(2,\,0)$ 不同
    这种情况与第 $3$ 种情况极其类似,用相同的方法做即可。注意判断 $n=m$ 的特殊情况。

考虑到转移是常系数的,使用矩阵加速可做到 $\mathrm O(\log N+\log M)$ 。

#include <iostream>

#include <algorithm>

#include <cstdio>

#include <cstring>

#define M 1000020

#define MOD 1000000007

using namespace std;

int f[M][2][2];

int Power(int x, int y)
{
    int o;

    if(y < 0)
        return 1;
    for(o = 1; y; y >>= 1)
    {
        if(y & 1)
            o = (long long)o * x % MOD;
        x = (long long)x * x % MOD;
    }

    return o;
}

int main(void) //game.cpp

{
    int n, m;
    int i, o;

    freopen("game.in" , "r", stdin );
    freopen("game.out", "w", stdout);

    cin >> n >> m;
    if(n > m)
        swap(n, m);
    if(n == 1)
        cout << Power(2, m) << endl;
    else if(n == 2)
        cout << (long long)4 * Power(3, m - 1) % MOD << endl;
    else if(n == 3)
        if(m == 1)
            cout << 8 << endl;
        else if(m == 2)
            cout << 36 << endl;
        else
            cout << (long long)112 * Power(3, m - 3) % MOD << endl;
    else
    {
        o = (long long)4 * Power(4, n - 2) % MOD * Power(3, m - n) % MOD * Power(2, n - 1) % MOD;
        o = (o + (long long)4 * 5 * Power(4, n - 4) % MOD * Power(3, m - n) % MOD * Power(2, n - 1) % MOD) % MOD;

        f[3][0][0] = 3;
        f[3][1][0] = 1;
        for(i = 4; i <= m; i ++)
        {
            f[i][0][0] = (long long)f[i - 1][1][0] * (i < n ? 3 : 2) % MOD;
            f[i][1][0] = f[i - 1][1][0];
            f[i][0][1] = (((long long)f[i - 1][0][1] + f[i - 1][1][1] * 2) * (i < n ? 2 : 1) % MOD + ((long long)f[i - 1][0][0] + f[i - 1][1][0]) * (i < n ? 3 : 2) % MOD) % MOD;
            f[i][1][1] = ((long long)f[i - 1][0][0] + f[i - 1][0][1] + f[i - 1][1][0] + f[i - 1][1][1] * 2) % MOD;
        }
        o = (o + ((long long)f[m][0][0] + f[m][1][0] + f[m][0][1] + f[m][1][1]) % MOD * Power(2, n - 2) % MOD * 2 % MOD) % MOD;

        memset(f, 0, sizeof(f));
        f[3][1][0] = 3;
        f[3][0][0] = 1;
        for(i = 4; i <= n; i ++)
        {
            f[i][1][0] = (long long)f[i - 1][0][0] * (i < m ? 3 : 2) % MOD;
            f[i][0][0] = f[i - 1][0][0];
            f[i][1][1] = (((long long)f[i - 1][1][1] + f[i - 1][0][1] * 2) * (i < m ? 2 : 1) % MOD + ((long long)f[i - 1][1][0] + f[i - 1][0][0]) * (i < m ? 3 : 2) % MOD) % MOD;
            f[i][0][1] = ((long long)f[i - 1][1][0] + f[i - 1][1][1] + f[i - 1][0][0] + f[i - 1][0][1] * 2) % MOD;
        }
        o = (o + ((long long)f[n][0][0] + f[n][1][0] + f[n][0][1] + f[n][1][1]) % MOD * Power(3, m - n - 1) % MOD * Power(2, n - 2) % MOD * 2 * (n < m ? 2 : 1) % MOD) % MOD;

        cout << o << endl;
    }

    return 0;
}

$\text{P6}$

$44\%$

对于每个询问,直接暴力进行树形 $\text{DP}$ 即可。

时间复杂度 $\mathrm O(NM)$ 。

$100\%$

记 $T(x)$ 为以 $x$ 为根的子树。

先考虑树的深度不深的时候怎么做:维护 $f(x,\,0/1)$ 表示在 $T(x)$ 中,是否选取 $x$,守护 $T(x)$ 内全部边的最小花费;$g(x,\,0/1)$ 表示在 $T(1)\setminus T(x)$ 之中,是否选取 $x$,守护 $T(1)\setminus T(x)$ 内所有边的最小花费。

对于询问 $(a,\,x,\,b,\,y)$,直接从 $a,\,b$ 开始走到 $\mathrm{LCA}(a,\,b)$ 处,路上进行 $\text{DP}$,最后加上 $\mathrm{LCA}(a,\,b)$ 的 $g$ 值(需要对于是否选取了 $\mathrm{LCA}$ 分类讨论)。


为什么慢呢?每次需要完整地遍历链条。

考虑倍增优化,记录 $h(x,\,y,\,0/1,\,0/1)$ 表示在 $T(p)\setminus T(x)$($p$ 为 $x$ 的 $2^y$ 级祖先)中,是否选取 $x$,是否选取 $y$,守护 $T(p)\setminus T(x)$ 的最小花费。

$h$ 显然是可以在倍增的过程中求出来的。

处理询问的时候,分别从 $a,\,b$ 往上倍增,枚举中间点的选取情况即可。

如果想使得处理方法更简单,可以只实现 $a,\,b$ 是祖先与孩子的情况(即 $\mathrm{LCA}(a,\,b)=a$ 或者 $\mathrm{LCA}(a,\,b)=b$),另外的情况倍增上去之后枚举 $\mathrm{LCA}$ 状态,减去对应的 $f$ 值可以得到答案。

时间复杂度 $\mathrm O(N\log N+M\log N)$ 。

#include <iostream>

#include <algorithm>

#include <cstdio>

#include <vector>

#define N 100020

#define M 17

#define oo 9999999999999LL

using namespace std;

int a[N];
vector<int> e[N];
long long f[N][2], g[N][2], s[M][N][2][2];
int h[M][N], d[N];

void DP(int x, int p)
{
    int i;

    f[x][1] = a[x];
    for(i = 0; i < (signed)e[x].size(); i ++)
        if(e[x].at(i) != p)
        {
            d[e[x].at(i)] = d[x] + 1;
            DP(e[x].at(i), x);
            f[x][0] += f[e[x].at(i)][1];
            f[x][1] += min(f[e[x].at(i)][0], f[e[x].at(i)][1]);
        }

    return;
}

void Pushdown(int x, int p)
{
    int i;

    if(x)
    {
        g[x][0] = f[p][1] - min(f[x][0], f[x][1]) + g[p][1];
        g[x][1] = min(f[p][0] - f[x][1] + g[p][0], f[p][1] - min(f[x][0], f[x][1]) + g[p][1]);

        h[0][x] = p;
        s[0][x][0][0] = oo;
        s[0][x][0][1] = f[p][1] - min(f[x][0], f[x][1]);
        s[0][x][1][0] = f[p][0] - f[x][1];
        s[0][x][1][1] = s[0][x][0][1];
        for(i = 1; i < M; i ++)
        {
            h[i][x] = h[i - 1][h[i - 1][x]];
            s[i][x][0][0] = min(s[i - 1][x][0][0] + s[i - 1][h[i - 1][x]][0][0], s[i - 1][x][0][1] + s[i - 1][h[i - 1][x]][1][0]);
            s[i][x][0][1] = min(s[i - 1][x][0][0] + s[i - 1][h[i - 1][x]][0][1], s[i - 1][x][0][1] + s[i - 1][h[i - 1][x]][1][1]);
            s[i][x][1][0] = min(s[i - 1][x][1][0] + s[i - 1][h[i - 1][x]][0][0], s[i - 1][x][1][1] + s[i - 1][h[i - 1][x]][1][0]);
            s[i][x][1][1] = min(s[i - 1][x][1][0] + s[i - 1][h[i - 1][x]][0][1], s[i - 1][x][1][1] + s[i - 1][h[i - 1][x]][1][1]);
        }
    }

    for(i = 0; i < (signed)e[x].size(); i ++)
        if(e[x].at(i) != p)
            Pushdown(e[x].at(i), x);

    return;
}

int GetLCA(int u, int v)
{
    int i, t;

    t = d[u] - d[v];
    for(i = 0; i < M; i ++)
        if(t & (1 << i))
            u = h[i][u];
    if(u == v)
        return u;

    for(i = M - 1; i > -1; i --)
        if(h[i][u] != h[i][v])
        {
            u = h[i][u];
            v = h[i][v];
        }

    return h[0][u];
}

long long Solve(int x, int p, int y, int q)
{
    int i, t;
    long long o[2], v, k;

    if(d[x] < d[y])
    {
        swap(x, y);
        swap(p, q);
    }
    t = GetLCA(x, y);

    if(t == y)
    {
        t = d[x] - d[y];
        v = f[x][p];
        for(i = 0; i < M; i ++)
            if(t & (1 << i))
            {
                o[0] = s[i][x][p][0];
                o[1] = s[i][x][p][1];
                x = h[i][x];
                break;
            }
        for(i ++; i < M; i ++)
            if(t & (1 << i))
            {
                k = o[0];
                o[0] = min(o[0] + s[i][x][0][0], o[1] + s[i][x][1][0]);
                o[1] = min(k    + s[i][x][0][1], o[1] + s[i][x][1][1]);
                x = h[i][x];
            }
        o[q] += v + g[y][q];

        return o[q] >= oo ? -1 : o[q];
    }
    else
    {
        v = oo;
        o[0] = Solve(x, p, t, 0);
        o[1] = Solve(y, q, t, 0);
        if(o[0] != -1 && o[1] != -1)
            v = o[0] + o[1] - g[t][0] - f[t][0];

        o[0] = Solve(x, p, t, 1);
        o[1] = Solve(y, q, t, 1);
        if(o[0] != -1 && o[1] != -1)
            v = min(v, o[0] + o[1] - g[t][1] - f[t][1]);

        return v >= oo ? -1 : v;
    }

    throw;
}

int main(void) //defense.cpp

{
    int n, m, u, v, p, q;
    int i;

    freopen("defense.in" , "r", stdin );
    freopen("defense.out", "w", stdout);

    scanf("%d %d %*s", &n, &m);
    for(i = 0; i < n; i ++)
        scanf("%d", &a[i]);
    for(i = 1; i < n; i ++)
    {
        scanf("%d %d", &u, &v);
        e[-- u].push_back(-- v);
        e[   v].push_back(   u);
    }
    DP(0, 0);
    Pushdown(0, 0);

    while(m --)
    {
        scanf("%d %d %d %d", &u, &p, &v, &q);
        printf("%lld\n", Solve(-- u, p, -- v, q));
    }

    return 0;
}