HDU - 5799 This world need more Zhu 樹上莫隊

HDU - 5799

第一部分可以dfs序莫隊， 或者可以dsu on tree。

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include<bits/stdc++.h>
#define LL long long
#define LD long double
#define ull unsigned long long
#define fi first
#define se second
#define mk make_pair
#define PLL pair<LL, LL>
#define PLI pair<LL, int>
#define PII pair<int, int>
#define SZ(x) ((int)x.size())
#define ALL(x) (x).begin(), (x).end()
#define fio ios::sync_with_stdio(false); cin.tie(0)                     ;

#define ll long long

using namespace std;

const int N = 2e5 + 7;
const int inf = 0x3f3f3f3f;
const LL INF = 0x3f3f3f3f3f3f3f3f;
const int mod = (int)1e9 + 7;
const double eps = 1e-8;
const double PI = acos(-1);

template<class T, class S> inline void add(T &a, S b) {a += b; if(a >= mod) a -= mod;}
template<class T, class S> inline void sub(T &a, S b) {a -= b; if(a < 0) a += mod;}
template<class T, class S> inline bool chkmax(T &a, S b) {return a < b ? a = b, true : false;}
template<class T, class S> inline bool chkmin(T &a, S b) {return a > b ? a = b, true : false;}

//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

struct FastIO {
    static const int S = 1e7;
    int wpos;
    char wbuf[S];
    FastIO() : wpos(0) {}
    inline int xchar() {
        static char buf[S];
        static int len = 0, pos = 0;
        if (pos == len)
            pos = 0, len = fread(buf, 1, S, stdin);
        if (pos == len) exit(0);
        return buf[pos++];
    }
    inline int xuint() {
        int c = xchar(), x = 0;
        while (c <= 32) c = xchar();
        for (; '0' <= c && c <= '9'; c = xchar()) x = x * 10 + c - '0';
        return x;
    }
    inline int xint()
    {
        int s = 1, c = xchar(), x = 0;
        while (c <= 32) c = xchar();
        if (c == '-') s = -1, c = xchar();
        for (; '0' <= c && c <= '9'; c = xchar()) x = x * 10 + c - '0';
        return x * s;
    }
    inline void xstring(char *s)
    {
        int c = xchar();
        while (c <= 32) c = xchar();
        for (; c > 32; c = xchar()) * s++ = c;
        *s = 0;
    }
    inline void wchar(int x)
    {
        if (wpos == S) fwrite(wbuf, 1, S, stdout), wpos = 0;
        wbuf[wpos++] = x;
    }
    inline void wint(ll x)
    {
        if (x < 0) wchar('-'), x = -x;
        char s[24];
        int n = 0;
        while (x || !n) s[n++] = '0' + x % 10, x /= 10;
        while (n--) wchar(s[n]);
    }
    inline void wstring(const char *s)
    {
        while (*s) wchar(*s++);
    }
    ~FastIO()
    {
        if (wpos) fwrite(wbuf, 1, wpos, stdout), wpos = 0;
    }
} io;

const int LOG = 17;
int n, m, B, a[N];
vector<int> G[N];
int qus[N][5];
LL ans[N];

int in[N], ot[N], id[N], depth[N], idx;
int pa[N][LOG];

int qcnt;
struct Qus {
    int L, R, a, b, id, lca;
    bool operator < (const Qus &rhs) const {
        if(L / B != rhs.L / B) return L < rhs.L;
        else return R < rhs.R;
    }
} q[N];

int hs[N], hscnt;

void dfs(int u, int fa) {
    pa[u][0] = fa;
    depth[u] = depth[fa] + 1;
    for(int i = 1; i < LOG; i++) {
        pa[u][i] = pa[pa[u][i - 1]][i - 1];
    }
    for(auto &v : G[u]) {
        if(v == fa) continue;
        dfs(v, u);
    }
}

int getLca(int u, int v) {
    if(depth[u] < depth[v]) swap(u, v);
    int d = depth[u] - depth[v];
    for(int i = LOG - 1; ~i; i--) {
        if(d >> i & 1) {
            u = pa[u][i];
        }
    }
    if(u == v) return u;
    for(int i = LOG - 1; ~i; i--) {
        if(pa[u][i] != pa[v][i]) {
            u = pa[u][i];
            v = pa[v][i];
        }
    }
    return pa[u][0];
}

void dfs1(int u, int fa) {
    in[u] = ++idx;
    id[idx] = u;
    for(auto &v : G[u]) {
        if(v == fa) continue;
        dfs1(v, u);
    }
    ot[u] = idx;
}

void dfs2(int u, int fa) {
    in[u] = ++idx;
    id[idx] = u;
    for(auto &v : G[u]) {
        if(v == fa) continue;
        dfs2(v, u);
    }
    ot[u] = ++idx;
    id[idx] = u;
}

int c1[N], op[N];
LL c2[N];

inline void update1(int x, int op) {
    x = a[id[x]];
    c2[c1[x]] -= hs[x];
    c1[x] += op;
    c2[c1[x]] += hs[x];
}


void solve1() {
    qcnt = idx = 0;
    dfs1(1, 0);
    for(int i = 1; i <= m; i++) {
        if(qus[i][0] == 2) continue;
        q[++qcnt] = Qus{in[qus[i][1]], ot[qus[i][1]], qus[i][3], qus[i][4], i, 0};
    }
    B = sqrt(n) + 1;
    sort(q + 1, q + 1 + qcnt);
    for(int i = 0; i <= hscnt; i++) {
        c1[i] = 0;
    }
    for(int i = 0; i <= n; i++) {
        c2[i] = 0;
    }
    int l = 1, r = 0, L, R, a, b, id;
    for(int o = 1; o <= qcnt; o++) {
        L = q[o].L; R = q[o].R;
        a = q[o].a; b = q[o].b; id = q[o].id;
        while(r < R) update1(++r, 1);
        while(l > L) update1(--l, 1);
        while(r > R) update1(r--, -1);
        while(l < L) update1(l++, -1);
        ans[id] = __gcd(c2[a], c2[b]);
    }
}

inline void update2(int x) {
    x = id[x];
    c2[c1[a[x]]] -= hs[a[x]];
    c1[a[x]] += op[x];
    c2[c1[a[x]]] += hs[a[x]];
    op[x] = -op[x];
}

void solve2() {
    qcnt = idx = 0;
    dfs2(1, 0);
    for(int i = 1; i <= m; i++) {
        if(qus[i][0] == 1) continue;
        int a = qus[i][1], b = qus[i][2];
        int lca = getLca(a, b);
        if(lca == a) {
            q[++qcnt] = Qus{in[a], in[b], qus[i][3], qus[i][4], i, lca};
        }
        else if(lca == b) {
            q[++qcnt] = Qus{in[b], in[a], qus[i][3], qus[i][4], i, lca};
        }
        else {
            if(in[a] <= in[b]) q[++qcnt] = Qus{ot[a], in[b], qus[i][3], qus[i][4], i, lca};
            else q[++qcnt] = Qus{ot[b], in[a], qus[i][3], qus[i][4], i, lca};
        }
    }

    B = 4 * sqrt(n) + 1;
    sort(q + 1, q + 1 + qcnt);

    for(int i = 0; i <= hscnt; i++) {
        c1[i] = 0;
    }
    for(int i = 0; i <= n; i++) {
        op[i] = 1;
        c2[i] = 0;
    }

    int l = 1, r = 0, L, R, a, b, qid, lca;

    for(int o = 1; o <= qcnt; o++) {
        L = q[o].L; R = q[o].R;
        a = q[o].a; b = q[o].b;
        qid = q[o].id; lca = q[o].lca;
        while(r < R) update2(++r);
        while(l > L) update2(--l);
        while(r > R) update2(r--);
        while(l < L) update2(l++);
        if(lca != id[L] && lca != id[R]) {
            c2[c1[::a[lca]]] -= hs[::a[lca]];
            c1[::a[lca]]++;
            c2[c1[::a[lca]]] += hs[::a[lca]];
            ans[qid] = __gcd(c2[a], c2[b]);
            c2[c1[::a[lca]]] -= hs[::a[lca]];
            c1[::a[lca]]--;
            c2[c1[::a[lca]]] += hs[::a[lca]];
        }
        else {
            ans[qid] = __gcd(c2[a], c2[b]);
        }
    }
}


void init() {
    hscnt = idx = 0;
    for(int i = 1; i <= n; i++) {
        G[i].clear();
    }
}

char s[] = "Case #";

int main() {
//    freopen("test.txt", "r", stdin);
//    freopen("1.out", "w", stdout);
    int T, cas = 0;
//    scanf("%d", &T);
    T = io.xint();
    while(T--) {
//        scanf("%d%d", &n, &m);
        n = io.xint(); m = io.xint();
        init();
        for(int i = 1; i <= n; i++) {
//            scanf("%d", &a[i]);
            a[i] = io.xint();
            hs[++hscnt] = a[i];
        }
        for(int i = 1; i < n; i++) {
            int u, v;
//            scanf("%d%d", &u, &v);
            u = io.xint(); v = io.xint();
            G[u].push_back(v);
            G[v].push_back(u);
        }
        for(int i = 1; i <= m; i++) {
            for(int j = 0; j < 5; j++) {
//                scanf("%d", &qus[i][j]);
                qus[i][j] = io.xint();
            }
        }
        sort(hs + 1, hs + 1 + hscnt);
        hscnt = unique(hs + 1, hs + 1 + hscnt) - hs - 1;
        for(int i = 1; i <= n; i++) {
            a[i] = lower_bound(hs + 1, hs + 1 + hscnt, a[i]) - hs;
        }
        dfs(1, 0);
        solve1();
        solve2();
//        printf("Case #%d:\n", ++cas);
        io.wstring(s);
        io.wint(++cas);
        io.wchar(':');
        io.wchar('\n');
        for(int i = 1; i <= m; i++) {
//            printf("%lld\n", ans[i]);
            io.wint(ans[i]);
            io.wchar('\n');
        }
    }
    return 0;
}

/*
*/