题目大意

一棵动态连边的有根树上，查询链上最小边权，要求必须是儿子走向父亲，否则输出\(0\)。
强制在线，\(n\leq 10^5\)，操作数\(m\leq 10^6\)，不会有重边。

分析

一种做法是，连边\((a,b)\)时暴力修改\(a\)子树里所有点的倍增数组，然后询问时用倍增数组计算答案。

显然，每次暴力修改涉及的点是\(O(n)\)级别的，修改复杂度就是\(O(n^2logn)\)。

如果采用启发式合并，强制把从大小较小的连通块连向大小较大的连通块，这时每个点被暴力修改的次数是\(O(logn)\)次，每次修改是\(O(logn)\)的复杂度，修改复杂度就降为\(O(nlog^2n)\)。

由于你强行改变的了树的父亲方向，当询问\((u,v)\)时，\(u\)到\(lca\)路径上所有边的原方向和树的父亲方向一致（注：父亲方向指由儿子走向父亲的方向），\(v\)到\(lca\)路径上所有边的原方向和树的父亲方向相反，这样才能在原树上从\(u\)到\(v\)。那么倍增数组要多维护两个，分别表示是否有原方向和父亲方向一致的边，是否有原方向与父亲方向相反的边，再注意两个点本就不连通的情况，这题就搞定了。

时间复杂度\(O(nlog^2n+mlogn)\)，要注意常数。

Code

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 100007;

inline int read()
{
    int x = 0, f = 0;
    char c = getchar();
    for (; c < '0' || c > '9'; c = getchar()) if (c == '-') f = 1;
    for (; c >= '0' && c <= '9'; c = getchar()) x = (x << 1) + (x << 3) + (c ^ '0');
    return f ? -x : x;
}
inline int min(int a, int b)
{
    if (a < b) return a;
    return b;
}

int n, m, fa[N], size[N];
int opt, a, b, c, lastans, flag, ta, tb;
int tot, h, t, st[N], to[N << 1], nx[N << 1], dir[N << 1], val[N << 1], q[N];
void add(int u, int v, int w, int c) { to[++tot] = v, nx[tot] = st[u], dir[tot] = w, val[tot] = c, st[u] = tot; }
int anc[N][17], mi[N][17], tag[2][N][17], dep[N];

inline int getfa(int x) { return fa[x] == x ? x : getfa(fa[x]); }

int getans(int u, int v)
{
    int f = 0, ans = 0x3f3f3f3f;
    if (dep[u] < dep[v]) swap(u, v), f ^= 1;
    for (int i = 16; i >= 0; --i) if (dep[anc[u][i]] >= dep[v])
    {
        if (tag[f][u][i]) return 0;
        ans = min(ans, mi[u][i]), u = anc[u][i];
    }
    if (u == v) return ans;
    for (int i = 16; i >= 0; --i) if (anc[u][i] != anc[v][i])
    {
        if (tag[f][u][i] || tag[!f][v][i]) return 0;
        ans = min(ans, min(mi[u][i], mi[v][i])), u = anc[u][i], v = anc[v][i];
    }
    if (!anc[u][0] && !anc[v][0]) return 0;
    if (tag[f][u][0] || tag[!f][v][0]) return 0;
    ans = min(ans, min(mi[u][0], mi[v][0]));
    return ans;
}

int main()
{
    //freopen("money.in", "r", stdin);
    //freopen("money.out", "w", stdout);
    
    n = read(), m = read();
    for (int i = 1; i <= n; ++i) fa[i] = i, size[i] = 1, dep[i] = 1;
    for (int i = 1; i <= m; ++i)
    {
        opt = read();
        if (opt)
        {
            a = read(), b = read(), a = (a + lastans) % n + 1, b = (b + lastans) % n + 1;
            printf("%d\n", lastans = getans(a, b));
        }
        else
        {
            a = read(), b = read(), c = read(), a = (a + lastans) % n + 1, b = (b + lastans) % n + 1, c = (c + lastans) % n + 1, flag = 0, ta = a, tb = b;
            add(b, a, 0, c), add(a, b, 1, c);
            ta = getfa(a), tb = getfa(b);
            if (size[ta] > size[tb]) swap(a, b), swap(ta, tb), flag ^= 1;
            fa[ta] = tb, size[tb] += size[ta], anc[a][0] = b, mi[a][0] = c, tag[0][a][0] = flag, tag[1][a][0] = !flag, dep[a] = dep[b] + 1;
            h = 1, q[t = 1] = a;
            while (h <= t)
            {
                int u = q[h]; ++h;
                for (int i = 1; i <= 16; ++i)
                {
                    anc[u][i] = anc[anc[u][i - 1]][i - 1];
                    mi[u][i] = min(mi[u][i - 1], mi[anc[u][i - 1]][i - 1]);
                    tag[0][u][i] = (tag[0][u][i - 1] | tag[0][anc[u][i - 1]][i - 1]);
                    tag[1][u][i] = (tag[1][u][i - 1] | tag[1][anc[u][i - 1]][i - 1]);
                }
                for (int i = st[u]; i; i = nx[i])
                    if (to[i] != anc[u][0])
                        anc[to[i]][0] = u, mi[to[i]][0] = val[i], tag[0][to[i]][0] = dir[i], tag[1][to[i]][0] = !dir[i], dep[to[i]] = dep[u] + 1, q[++t] = to[i];
            }
        }
    }
    return 0;
}

【JZOJ6273】【NOIP提高组A】欠钱 (money)

原文：https://www.cnblogs.com/zjlcnblogs/p/11300120.html