前言

本次比赛其实出的很心急，主要原因是出题人在应该出题的时间做木工（摆烂）去了。但是幸运的是最后还是出完了题目。

本次比赛有一个比较坑的点，我把难度顺序倒过来排了，因为 2022 年 NOIP 的 T3 比 T2 简单，曾经坑死了我（我的省一啊啊啊啊啊），所以我打算把这次比赛难度也倒过来排。

相遇

我们先找到 a,b 的 lca，设为 x，找到 c,d 的 lca，设为 y。如果 x,y 的 lca 不是 x 或者 y 中任何一个，那么说明 a,b 和 c,d 的路径在不同的子树上，显然不会相交。接下来开始分类讨论，先判断 x,y 的 lca 是谁。这里我们先假设它是 x，那么就说明 y 在 x 的子树底下，接下来我们就只要判断 y 的子树当中是否包含 a,b 中的一个，如果包含，那么 y 显然会在 a,b 的路径上，否则就说明 y 和 a,b 在不同的子树上，路径不会相交。对于 x,y 的 lca 是 y 的情况，也类似讨论即可。

#include <bits/stdc++.h>

using namespace std;

constexpr int MAX_N = 100010;
vector<int> G[MAX_N];

int dep[MAX_N], siz[MAX_N], par[MAX_N], hs[MAX_N];
void dfs1(int x)
{
    siz[x] = 1;
    for (auto it : G[x]) {
        if (it == par[x]) {
            continue;
        }
        par[it] = x;
        dep[it] = dep[x] + 1;
        dfs1(it);
        siz[x] += siz[it];
        if (!hs[x] || siz[hs[x]] < siz[it]) {
            hs[x] = it;
        }
    }
}

int top[MAX_N];
void dfs2(int x, int tx)
{
    top[x] = tx;
    if (hs[x]) {
        dfs2(hs[x], tx);
    }
    for (auto it : G[x]) {
        if (it == hs[x] || it == par[x]) {
            continue;
        }
        dfs2(it, it);
    }
}

int lca(int u, int v)
{
    while (top[u] != top[v]) {
        if (dep[top[u]] > dep[top[v]]) {
            u = par[top[u]];
        } else {
            v = par[top[v]];
        }
    }
    return dep[u] > dep[v] ? v : u;
}

int main()
{
    cin.tie(nullptr);
    cout.tie(nullptr);
    ios::sync_with_stdio(false);
    int n, q;
    cin >> n >> q;
    int u, v;
    for (int i = 1; i <= n - 1; i++) {
        cin >> u >> v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    dep[1] = 1;
    par[1] = 0;
    dfs1(1);
    dfs2(1, 0);
    int a, b, c, d;
    for (int i = 1; i <= q; i++) {
        cin >> a >> b >> c >> d;
        int x = lca(a, b);
        int y = lca(c, d);
        int k = lca(x, y);
        if (k == x) {
            if (lca(a, y) == y) {
                cout << "Y" << endl;
            } else if (lca(b, y) == y) {
                cout << "Y" << endl;
            } else {
                cout << "N" << endl;
            }
        } else if (k == y) {
            if (lca(c, x) == x) {
                cout << "Y" << endl;
            } else if (lca(d, x) == x) {
                cout << "Y" << endl;
            } else {
                cout << "N" << endl;
            }
        } else {
            cout << "N" << endl;
        }
    }
    return 0;
}

异或

这题稍微有点思维（其实没有）。异或常用三大定律：交换律，结合律，自反律。这里主要用到的是自反律:$axorbxorb=a$，这就意味着，我可以求出异或的前缀，然后分段的时候除一下就行。

当然，根据交换律和结合律，这题显然也可以用线段树，不过何苦呢。

#include <bits/stdc++.h>

using namespace std;

int a[100000];

int main()
{
    int n, q;
    cin >> n >> q;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        a[i] ^= a[i - 1];
    }
    int l, r;
    for (int i = 1; i <= q; i++) {
        cin >> l >> r;
        cout << (a[r] ^ a[l - 1]) << endl;
    }
    return 0;
}

勾股

签到题，模拟即可。

#include <bits/stdc++.h>

using namespace std;

int main()
{
    long long m, n;
    cin >> m >> n;
    vector<long long> temp = { 2 * m * n, m * m - n * n, m * m + n * n };
    sort(temp.begin(), temp.end());
    cout << temp[0] << ' ' << temp[1] << ' ' << temp[2] << endl;
    return 0;
}

import Data.List

main = do
    [m, n] <- fmap (map read . words) getLine
    putStrLn $ foldl (\acc x -> acc ++ show x ++ " ") [] $ sort [2 * m * n, m * m - n * n, m * m + n * n]