悬崖边的踟蹰 —— CSP-S 2019

2019-11-18
游记
spinner.svg 次阅读

文章目录

【注意】最后更新于 March 29, 2020，文中内容可能已过时，请谨慎使用。

标题来自 三月のライオン Chapter.64 銀の羽根 ：

答案只在漆黑的水底。

越是前进，下一个答案就只能在更深的地方找到。

以前越是潜入，就能获得答案。

比起恐怖，欲望更胜一筹。

但是成为职业棋手 6 年后，如今变得完全不能前进。

即便带着要撕碎全身的想法去潜入，但是却空手而回，已经是很常见的事了。

比起 「也许能找到」，「反正又不一定能找到」这个念头胜利的时候，就只能进行有限的努力了。

但是，桐山和二海堂无视了那样的我。

理所当然一样无论多少次都跳入其中。根本就不正常。

他们即便屡次空手而归，也会制定对策继续挑战。

丝毫不介意痛苦，无论多少次都投身其中。

只留下，被恐惧压倒的我。

Day 1

像往常一样，听了 YUKI 的两首三狮 OP 和 IOI2018 主题曲，抽签进考场。

由于自己还算小有名气，这次也不是 NOI 或是什么比赛，只是 CSP，于是避开了人群，也并没有人过来搭话。大概不露出准考证上的名字的话，其他人要么不认识我，要么已经退役了，要么知道我实际上有多菜吧。

T1 当然是看完题就会做了。$n\le 64$ 真毒瘤，只不过给个 $95%$ 的 $k\le 2^{63}-1$ 提示太明显了（然而后 $50%$ 的数据 $n$ 还是可以到 $64$…不知道有没有这样的数据）。

T2 一开始想了个神秘的树套树做法，感觉非常蠢，于是去看 T3，发现并不会做，就把 T2 的 $O(n^3)$ 和 T3 的暴力写了。

写完之后想到了若干 T2 的假做法，然后想到了一个略麻烦的线性做法，只不过写起来也没花太多时间。拍上的时候已经 10:30 了，好像比大众 AC 时间 9:00 晚了不少。

之后开始自闭。大概 11:20 的时候去上了个厕所，想到了个感觉挺对的做法：把删边视作给边编号，每个点出发先走编号最小的出边，然后走来到当前点的边在当前点出边中编号的后继。于是可以关于每个点用链表维护一个出边的顺序，再枚举每个数字，DFS 求出它的终点可以在哪些位置，选择其中最小的一个。感觉挺难写的，11:54 的时候算是写完了，但由于赶时间几乎是乱写的，测样例 RE 了，于是就注释掉了，换成了暴力。

我是从学 OI 一个月起就 using namespace std; 的选手，但这次就突然想不 using 来防止 CE，而且每题都在 NOI Linux 虚拟机下编译了，但 11:58 的时候突然发现自己 T3 暴力的 next_permutation 没有加 std，不是很清楚为什么不会 CE，当时的代码也没有了，可能是我哪看错了，总之我最后是把 using namespace std; 加上了..

所以说不要试图在考场上改代码习惯。

考场须知的签名是在监考说考试结束之后写的，写的时候手都在抖..所以说最后 10min 都别写代码了，5min 根本不够。

考完立刻出了考场，无视掉身边所有人，假装世界上只有自己一个人考了 CSP（

然后由于最后搞得有点紧张，还有神秘的 std::next_permutation 事件，一直担心文件错误 / CE 。于是就下了一下午（酒馆战）棋，试图忘掉 Day 1。

可是屏蔽 QQ 并不能妨碍我妈晚餐时告诉我人均 210，myh AK 之类的。

Day 2

今天是一次崭新的比赛（自我洗脑成功）。

依然是 YUKI 的两首三狮 OP 和 IOI2018 主题曲，然而因为估错时间，为了避免听车载广播，多听了一遍 Euphoria 。

今天不用校内集合，然而考场在 8 楼，于是要坐电梯。只不过还是没人过来搭话。

T1，怎么是计数啊（

看了几分钟感觉不太会做，人要懵了，这是 D2T1 吗（

冷静了一下，想到一个假的 $O(n^2m)$ 做法。

然后去看 T2，怎么办我只会 $O(n^3)$..但 $O(n^2)$ 好像很可做的样子。

然后去看 T3，怎么办我只会 $O(n^2)$..但链和菊花好像很可做的样子。

写 T1 写到一半，发现自己假了。冷静了一下，想到一个 $O(n^3m)$ 做法。8700k 应该啥都能过吧.png

写完一测，4.8s，人没了。

卡了卡常，3.6s，人没了。

开 O2，1.2s。但要是手开 O2 我就真没了。怎么手写取模优化啊.png

然后去写 T2，还没开始写就发现可以 $O(n^2\log n)$。写完一测，5s，我又没了。发现多次二分可以用双指针（在 一些注意事项 中有），于是就 $O(n^2)$ 了，跑的挺快。

然后去写 T3。$O(n^2)$ 挺好写的。链好像很简单。完美二叉树是啥..手画一下，发现剩下来较大的那部分的重心只能是根或根的儿子或根和根的儿子，于是也很好写。

此时 11:00 了。

为什么我不会做 D2T1 啊..于是选择去看 T1。这个背包可以 NTT 优化吗..在脑内思考了 5s NTT 是否应当出现在 CSP 中后，我成功算错了复杂度，以为它是 $O(n^2m\log)$ 的，然后写了个极限数据跑 80s 的 $O(n^2m\log^2)$…

最后也没有获得更多分数了。只不过这天提前 10min 就开始检查文件相关问题了。而且全部都 using namespace std; 了，也在 NOI Linux 下编译了。感觉挺放心的。

这次出来没有直接跑掉，然后就听说闫老师 A 了 T1，T2 88。还听说华一前几天校内讲了 T2..

在回家的路上被告知下午要去学校上 whk..然后书包都没拿（实际上书包里也没有任何 whk 相关的东西），吃完饭就去了，还迟到了 5min。

听说是与前段时间内容无关的物理课，然后还真是与前面的电学无关的动量，给人的感觉几乎是接着我停课前往后讲，于是还算顺畅。

选修 3-5 后面的几章还稍微有一点点涉及电学内容，量子力学什么的也没有完全看懂，计算什么的都跳过了，然而我晚自习就顺着把书看完了（感觉看完后啥都没学会）。

Day 3

上午是快乐的 whk 生活。语文课讲期中考试卷子，我就拿别人的卷子看了下上面的几篇阅读。数学课讲求导，于是就写了下物理作业（没毛病）。化学课完全自闭了，于是就写完了物理作业（另一种意义上的没毛病）。

下午好像啥都没干，看着闫老师和肖老师拿民间数据测全省，然后发现 jxl 可能 535…

晚上写游记。

然后发现 D1T3 wqy 的题解好像和我的思路差不多，就试图拿我的考场代码调，发现调不出来，就重写了一遍，调过小样例之后获得了链的 25 分..

Day 4

今天上了一整天 whk，上午还是化学自闭，其它课还好，下午是体检 & 地理 & 政治（马上学考了）。

晚上过来给 UOJ #487 加了个负自环的样例，稍微修了下题面。第一次用 svn。（并不知道 UOJ 社区版把 svn 阉割掉之后怎么远程下载数据，只不过 Hinata Online Judge 是资瓷的。）

然后继续调 D1T3，一开始用 $n=10$ 的数据调自闭了，对拍出 $n=4$ 的数据之后 5min 就调出来了..

感觉要是头脑清醒而且像兔那样 30min AC T1T2，还是能在考场上写出来的..

题解

D1T1

依题意模拟，记得开 unsigned long long 。

考场代码 
#include <iostream>
#include <cstdio>

typedef unsigned long long ull;

void solve(int n, ull k)
{
    if (n == 0) return;
    if (k < (1ull << (n - 1)))
    {
        std::cout << 0;
        solve(n - 1, k);
    }
    else
    {
        std::cout << 1;
        solve(n - 1, (1ull << (n - 1)) - 1 - (k & ((1ull << (n - 1)) - 1)));
    }
}

int main()
{
    int n;
    ull k;

    std::cin >> n >> k;

    solve(n, k);

    puts("");

    return 0;
}

D1T2

我的考场做法好像比较麻烦..

大致思路是定义一个点的权值是它到根的路径上左括号个数减去右括号个数，并且维护每个点向上多少个点满足右括号个数之和不少于左括号个数之和，后面这个东西维护的时候要分几种情况讨论。

维护了这两个信息，每个点新增的合法括号串就是一段区间里权值为某个数的点的个数，离线下来就可以 $O(n)$ 且无需高级数据结构地解决了。

考场代码 
#include <iostream>
#include <cstdio>
#include <vector>
#include <string>
#include <fstream>

using std::cin;
using std::string;
using std::vector;

typedef long long ll;
typedef std::pair<int, int> pii;

int n;
string s, t;
vector<ll> ans;
vector<vector<int> > g;
vector<vector<pii> > q;
vector<int> jump, tot, pa;

void dfs(int u, int cnt)
{
    cnt += s[u - 1] == '(' ? 1 : -1;
    if (s[u - 1] == ')') ans[u] = tot[cnt + n];
    if (u == 1) jump[u] = 1;
    else if (s[u - 1] == ')') jump[u] = jump[pa[jump[pa[u]]]];
    else if (s[pa[u] - 1] == ')') jump[u] = jump[pa[pa[u]]];
    else jump[u] = u;
    if (s[u - 1] == ')') q[pa[pa[jump[pa[u]]]]].push_back(pii(u, cnt));
    ++tot[cnt + n];
    for (int i = 0; i < g[u].size(); ++i) dfs(g[u][i], cnt);
    for (int i = 0; i < q[u].size(); ++i) ans[q[u][i].first] -= tot[q[u][i].second + n];
    --tot[cnt + n];
}

int main()
{
    cin >> n >> s;

    g.resize(n + 1);
    q.resize(n + 1);
    ans.resize(n + 1);
    pa.resize(n + 1, 0);
    jump.resize(n + 1, 1);
    tot.resize(2 * n + 1, 0);

    for (int i = 2; i <= n; ++i)
    {
        cin >> pa[i];
        g[pa[i]].push_back(i);
    }

    jump[0] = 1;

    tot[n] = 1;
    dfs(1, 0);

    ll out = ans[1];

    for (int i = 2; i <= n; ++i)
    {
        ans[i] += ans[pa[i]];
        out ^= ans[i] * i;
    }

    std::cout << out << std::endl;

    return 0;
}

D1T3

（我在游记里说过大致思路了。）

把删边视作给边编号，每个点出发先走编号最小的出边，然后走来到当前点的边在当前点出边中编号的后继。于是可以关于每个点用链表维护一个出边的顺序，再枚举每个数字，DFS 求出它的终点可以在哪些位置，选择其中最小的一个。

然后会发现有很多细节，使用并查集会比链表好写一些（虽然复杂度会略微大一点点）。

代码是调试了一万遍写出来的，可能有地方会有些冗余..

参考代码 
#include <iostream>
#include <cstdio>
#include <vector>

using namespace std;

vector<bool> able; 
vector<vector<bool> > haspre;
vector<int> a, pa, ans, head, tail;
vector<vector<int> > f, g, nxt, siz;

int find(int u, int x)
{
    return x == f[u][x] ? x : f[u][x] = find(u, f[u][x]);
}

void dfs(int u)
{
    if (!pa[u])
    {
        if (head[u])
        {
            int v = head[u];
            pa[v] = u;
            dfs(v);
        }
        else
        {
            for (int i = 0; i < g[u].size(); ++i)
            {
                int v = g[u][i];
                if (!haspre[u][v] && !(tail[u] && find(u, v) == find(u, tail[u]) && siz[u][find(u, v)] < g[u].size()))
                {
                    pa[v] = u;
                    dfs(v);
                }
            }
        }
    }
    else
    {
        if (nxt[u][pa[u]])
        {
            int v = nxt[u][pa[u]];
            pa[v] = u;
            dfs(v);
        }
        else
        {
            if (!tail[u] && !(find(u, pa[u]) == find(u, head[u]) && siz[u][find(u, head[u])] < g[u].size())) able[u] = true;
            if (find(u, pa[u]) != find(u, tail[u]))
            {
                for (int i = 0; i < g[u].size(); ++i)
                {
                    int v = g[u][i];
                    if (find(u, v) != find(u, head[u]) && find(u, pa[u]) != find(u, v) && !haspre[u][v] &&
                        !(find(u, pa[u]) == find(u, head[u]) && find(u, v) == find(u, tail[u]) && siz[u][find(u, pa[u])] + siz[u][find(u, v)] < g[u].size()))
                    {
                        pa[v] = u;
                        dfs(v);
                    }
                }
            }
        }
    }
}

void apply(int u, int from)
{
    if (!from) tail[u] = pa[u];
    else if (!pa[u])
    {
        head[u] = from;
        return;
    }
    else
    {
        nxt[u][pa[u]] = from;
        haspre[u][from] = true;
        siz[u][find(u, from)] += siz[u][find(u, pa[u])];
        f[u][find(u, pa[u])] = find(u, from);
    }
    apply(pa[u], u);
}

int main()
{
    int T;

    cin >> T;

    while (T--)
    {
        int n;

        cin >> n;

        a.resize(n + 1);
        ans.resize(n + 1);
        head.assign(n + 1, 0);
        tail.assign(n + 1, 0);
        g.assign(n + 1, vector<int>());
        f.assign(n + 1, vector<int>(n + 1, 0));
        siz.assign(n + 1, vector<int>(n + 1, 1));
        nxt.assign(n + 1, vector<int>(n + 1, 0));
        haspre.assign(n + 1, vector<bool>(n + 1, false));

        for (int i = 1; i <= n; ++i) cin >> a[i];

        for (int i = 1; i < n; ++i)
        {
            int u, v;
            cin >> u >> v;
            g[u].push_back(v);
            g[v].push_back(u); 
            f[u][v] = v;
            f[v][u] = u;
        }

        if (n == 1)
        {
            puts("1");
            continue;
        }

        for (int i = 1; i <= n; ++i)
        {
            able.assign(n + 1, false);
            pa.assign(n + 1, 0);
            dfs(a[i]);
            for (int j = 1; j <= n; ++j)
            {
                if (able[j])
                {
                    cout << j << " \n"[i == n];
                    apply(j, 0);
                    break;
                }
            }
        }
    }

    return 0;
}

D2T1

首先可以通过 $O(n^2)$ 的 DP 求出没有 Yazid 的限制（每种主要食材不超过一半）的答案。

然后枚举每种主要食材，算出超过一半的方案数。

两部分答案相减即为最终答案。

第一部分比较简单，我猜大家都会，毕竟这是个基本的背包问题..

第二部分的话，枚举主要食材后有一个比较容易想到的 $O(n^3)$ DP，但应该是无法通过本题的。

这个 $O(n^3)$ DP 计算了使用多少种当前枚举的食材以及多少种非当前枚举的食材的方案数，但实际上我们并不关心这两种情况具体有多少种食材，而只关心它们的差，所以可以得到下面这种 $O(n^2)$ 的 DP 方法：

令 $f_{i, j}$ 表示使用 $1\sim i$ 这些烹饪方法，做了 $x$ 道当前枚举的食材，$x-j$ 道非当前枚举的食材，的方案数。令当前枚举的食材为 $t$ 。

转移有三种情况，不做/做枚举的/做非枚举的，所以，$f_{i,j}=f_{i-1,j}+a_{i,t}f_{i-1,j-1}+\left(\left(\sum_{p=1}^m a_{i, p}\right)-a_{i,t}\right)f_{i-1,j+1}$ 。

对第二部分答案的贡献是 $\sum_{i=1}^nf_{n,i}$ 。

总复杂度 $O(n^2m)$ 。

参考代码 
#include <iostream>
#include <cstdio>
#include <vector>

using namespace std;

typedef long long ll;

const int mod = 998244353;

int n, m, ans;
vector<int> sum;
vector<vector<int> > a, f;

int main()
{
    scanf("%d%d", &n, &m);

    sum.resize(n + 1, 0);
    a.resize(n + 1, vector<int>(m + 1));

    for (int i = 1; i <= n; ++i)
    {
        for (int j = 1; j <= m; ++j)
        {
            scanf("%d", &a[i][j]);
            sum[i] = (sum[i] + a[i][j]) % mod;
        }
    }

    f.resize(n + 1, vector<int>(n + 1, 0));
    f[0][0] = 1;

    for (int i = 1; i <= n; ++i)
    {
        f[i][0] = 1;
        for (int j = 1; j <= i; ++j)
        {
            f[i][j] = (f[i - 1][j] + (ll) f[i - 1][j - 1] * sum[i]) % mod;
        }
    }

    for (int i = 1; i <= n; ++i) ans = (ans + f[n][i]) % mod;

    for (int i = 1; i <= m; ++i)
    {
        f.assign(n + 1, vector<int>(2 * n + 3, 0));
        f[0][n + 1] = 1; // 下标加上 n+1 避免负数下标
        for (int j = 1; j <= n; ++j)
        {
            for (int k = n + 1 - j; k <= n + 1 + j; ++k)
            {
                f[j][k] = ((ll) a[j][i] * f[j - 1][k - 1] + (ll) (sum[j] - a[j][i] + mod) * f[j - 1][k + 1] + f[j - 1][k]) % mod;
            }
        }
        for (int j = n + 2; j <= n * 2 + 1; ++j) ans = (ans - f[n][j] + mod) % mod;
    }

    cout << ans;

    return 0;
}

D2T2

首先是一个结论：最后一个断点最大的解是最优解。证明请参考 myy 的题解。（因为自己并没有想到什么更加简洁的证法..）（当然还可以打表发现。）

有了这个结论之后，令 $f_i$ 表示 $[1,i]$ 这段的最后一个断点的最大值，那么，$f_i=\max\{j|j\in\mathbb{N},(\sum_{t=f_j+1}^ja_t)\le(\sum_{t=j+1}^ia_t)\}$ 。

预处理前缀和 $pre[i]=\sum_{j=1}^ia_i$，那么 $f_{i}=\max\{j|j\in\mathbb{N},2pre[j]-pre[f_j]\le pre[i]\}$ ，然后就可以用单调队列优化了。

需要高精的只有最后的答案计算，这可以用 __int128 实现。

参考代码 
#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;

struct IO {
#define MAXSIZE (1 << 20)
#define isdigit(x) (x >= '0' && x <= '9')
    char buf[MAXSIZE], *p1, *p2;
    char pbuf[MAXSIZE], *pp;
#if DEBUG
#else
    IO() : p1(buf), p2(buf), pp(pbuf) {}
    ~IO() { fwrite(pbuf, 1, pp - pbuf, stdout); }
#endif
    inline char gc() {
#if DEBUG
        return getchar();
#endif
        if (p1 == p2) p2 = (p1 = buf) + fread(buf, 1, MAXSIZE, stdin);
        return p1 == p2 ? ' ' : *p1++;
    }
    inline bool blank(char ch) {
        return ch == ' ' || ch == '\n' || ch == '\r' || ch == '\t';
    }
    template <class T>
        inline void read(T &x) {
        register double tmp = 1;
        register bool sign = 0;
        x = 0;
        register char ch = gc();
        for (; !isdigit(ch); ch = gc())
            if (ch == '-') sign = 1;
        for (; isdigit(ch); ch = gc()) x = x * 10 + (ch - '0');
        if (ch == '.')
            for (ch = gc(); isdigit(ch); ch = gc())
                tmp /= 10.0, x += tmp * (ch - '0');
        if (sign) x = -x;
    }
    inline void read(char *s) {
        register char ch = gc();
        for (; blank(ch); ch = gc())
            ;
        for (; !blank(ch); ch = gc()) *s++ = ch;
        *s = 0;
    }
    inline void read(char &c) {
        for (c = gc(); blank(c); c = gc())
            ;
    }
    inline void push(const char &c) {
#if DEBUG
        putchar(c);
#else
        if (pp - pbuf == MAXSIZE) fwrite(pbuf, 1, MAXSIZE, stdout), pp = pbuf;
        *pp++ = c;
#endif
    }
    template <class T>
        inline void write(T x) {
        if (x < 0) x = -x, push('-');
        static T sta[35];
        T top = 0;
        do {
            sta[top++] = x % 10, x /= 10;
        } while (x);
        while (top) push(sta[--top] + '0');
    }
    template <class T>
        inline void write(T x, char lastChar) {
        write(x), push(lastChar);
    }
} io;

const int N = 4e7 + 5;

typedef long long ll;

ll a[N];
int n, type, f[N], q[N], ql = 1, qr;

ll calc(int x)
{
    return a[x] * 2 - a[f[x]];
}

void write(__int128 x)
{
    if (x > 9) write(x / 10);
    putchar(x % 10 + '0');
}

int main()
{
    io.read(n);
    io.read(type);

    if (type == 0) for (int i = 1; i <= n; ++i) io.read(a[i]);
    else
    {
        int x, y, z, b, c, m;
        io.read(x);
        io.read(y);
        io.read(z);
        io.read(b);
        io.read(c);
        io.read(m);

        int k = 1;

        for (int i = 1; i <= m; ++i)
        {
            int p, l, r;
            io.read(p);
            io.read(l);
            io.read(r);
            while (k <= p)
            {
                int t;
                if (k == 1) t = b;
                else if (k == 2) t = c;
                else
                {
                    t = ((ll) x * c + (ll) y * b + z) & ((1 << 30) - 1);
                    b = c;
                    c = t;
                }
                a[k++] = t % (r - l + 1) + l;
            }
        }
    }

    for (int i = 2; i <= n; ++i) a[i] += a[i - 1];

    for (int i = 1; i <= n; ++i)
    {
        while (ql < qr && calc(q[ql + 1]) <= a[i]) ++ql;
        if (ql > qr || calc(q[ql]) > a[i]) f[i] = 0;
        else f[i] = q[ql];
        ll tmp = calc(i);
        while (ql <= qr && tmp <= calc(q[qr])) --qr;
        q[++qr] = i;
    }

    __int128 ans = 0;

    for (int i = n; i; i = f[i]) ans += (__int128) (a[i] - a[f[i]]) * (a[i] - a[f[i]]);

    write(ans);

    return 0;
}

D2T3

怎么今年 D2T3 又是 NOI 选手们纷纷用神仙做法秒掉，然后题解区窜出一个神奇的倍增做法（

瞟了眼主席树题解，感觉自己大约能想出来，于是去学习了一下神奇的倍增做法：

进行树链剖分（实际上只用求出重儿子而不用进行剖分），有一个性质：如果重心在一个子树内，且这个子树的根不是重心，那么重心一定在根的重儿子那棵子树里。

（如果有多个儿子大小一样，重心只能是根。）

然后就可以向下倍增找到重心（如果跳过去之后“向上”的子树大小不超过总点数一半就跳过去）。找到之后还要判其父亲是否也是重心。

然而这样只能处理有根树的子树，另一半的子树（“向上”的子树）需要类似换根 DP 进行处理，需要分几种情况讨论，具体细节可以自行脑补 + 对拍发现自己漏了哪种情况。

参考代码 
#include <iostream>
#include <cstdio>
#include <cctype>
#include <vector>
#include <algorithm>

using namespace std;

typedef pair<int, int> pii;

int read()
{
    int out = 0;
    char c;
    while (!isdigit(c = getchar()));
    for (; isdigit(c); c = getchar()) out = out * 10 + c - '0';
    return out;
}

int n, dfntot;
long long ans;
vector<vector<int> > g, bz;
vector<int> dep, siz, pa, dfn, exi;

struct Val
{
    pii fi, se;
    Val()
    {
        fi = se = pii(0, 0);
    }
    void insert(pii x)
    {
        if (x > fi)
        {
            se = fi;
            fi = x;
        }
        else if (x > se) se = x;
    }
    pii get(pii x = pii(-1, -1))
    {
        if (x == fi) return se;
        return fi;
    }
};

vector<Val> son;

void dfs1(int u)
{
    siz[u] = 1;
    dfn[u] = ++dfntot;
    for (int i = 0; i < g[u].size(); ++i)
    {
        int v = g[u][i];
        if (v == pa[u]) continue;
        dep[v] = dep[u] + 1;
        pa[v] = u;
        dfs1(v);
        siz[u] += siz[v];
        son[u].insert(pii(siz[v], v));
    }
    exi[u] = dfntot;
    if (u == 1) return; 
    bz[u][0] = son[u].get().second;
    for (int i = 1; i <= 17; ++i) bz[u][i] = bz[bz[u][i - 1]][i - 1];
    int x = u;
    for (int i = 17; i >= 0; --i)
    {
        int v = bz[x][i];
        if (v && siz[u] - siz[v] <= siz[u] / 2) x = v;
    }
    ans += x;
    if (siz[x] <= siz[u] / 2) ans += pa[x];
}

bool judge(int u, int v)
{
    if (!v) return false;
    int f = pa[u];
    if (v == f) return true;
    if (dfn[f] >= dfn[v] && dfn[f] <= exi[v]) return siz[pa[v]] - siz[u] <= (n - siz[u]) / 2;
    return n - siz[u] - siz[v] <= (n - siz[u]) / 2;
}

bool judge2(int u, int v)
{
    if (v == u || !v) return false;
    int f = pa[u];
    if (dfn[f] >= dfn[v] && dfn[f] <= exi[v])
    {
        return n - siz[v] <= (n - siz[u]) / 2 && son[v].get(pii(siz[pa[v]], pa[v])).first <= (n - siz[u]) / 2;
    }
    return son[v].get().first <= (n - siz[u]) / 2;
}

void dfs2(int u)
{
    vector<int> tmp = bz[u];
    Val rson = son[u];
    int f = pa[u];
    int paf = pa[f];
    if (u != 1)
    {
        pa[f] = u;
        son[u].insert(pii(n - siz[u], f));
        bz[f][0] = son[f].get(pii(siz[u], u)).second;
        for (int i = 1; i <= 17; ++i) bz[f][i] = bz[bz[f][i - 1]][i - 1];
        int x = f;
        for (int i = 17; i >= 0; --i)
        {
            int v = bz[x][i];
            if (judge(u, v)) x = v;
        }
        ans += x;
        if (judge2(u, pa[x])) ans += pa[x];
    }
    for (int i = 0; i < g[u].size(); ++i)
    {
        int v = g[u][i];
        if (v == f) continue;
        dfs2(v);
    }
    bz[u] = tmp;
    pa[f] = paf;
    son[u] = rson;
}

int main()
{
    int T;

    T = read();

    while (T--)
    {
        n = read();

        bz.resize(n + 1, vector<int>(18, 0));
        g.assign(n + 1, vector<int>());
        son.assign(n + 1, Val());
        dep.resize(n + 1, 0);
        dfn.resize(n + 1, 0);
        exi.resize(n + 1, 0);
        siz.resize(n + 1, 0);
        pa.resize(n + 1, 0);

        ans = dfntot = 0;

        for (int i = 1; i < n; ++i)
        {
            int u = read();
            int v = read();
            g[u].push_back(v);
            g[v].push_back(u);
        }

        dfs1(1);
        dfs2(1);

        cout << ans << endl;
    }

    return 0;
}

文章作者 ouuan

上次更新 2020-03-29 (3d64fa3) ，更新历史

许可协议 CC BY-SA 4.0

评论正在加载中...如果评论较长时间无法加载，你可以 搜索对应的 issue 或者 新建一个 issue 。