CF1101

D:题意：树上每个顶点有个权值，求最长链，满足链上gcd > 1

解：对每个质数建虚树，每个点只会拆成log个点，所以是log²的。

#include <bits/stdc++.h>

const int N = 200010;

struct Edge {
    int nex, v, len;
}edge[N << 1], EDGE[N << 1]; int tp, TP;

int p[N], top, e[N], pos2[N], num2, ST[N << 1][20], pw[N << 2], n, ans, id[N], last[N];
int vis[N];
int imp[N], K, E[N], val[N], fa[N], d[N], stk[N], use[N], Time, RT, f[N];
std::vector<int> v[N];

inline void add(int x, int y) {
    tp++;
    edge[tp].v = y;
    edge[tp].nex = e[x];
    e[x] = tp;
    return;
}

inline void ADD(int x, int y) {
    TP++;
    EDGE[TP].v = y;
    EDGE[TP].len = d[y] - d[x];
    EDGE[TP].nex = E[x];
    E[x] = TP;
    return;
}

inline void getp(int n) {
    for(int i = 2; i <= n; i++) {
        if(!vis[i]) {
            p[++top] = i;
            last[i] = i;
            id[i] = top;
        }
        for(int j = 1; j <= top && i * p[j] <= n; j++) {
            vis[i * p[j]] = 1;
            last[i * p[j]] = p[j];
            if(i % p[j] == 0) break;
        }
    }
    return;
}

void DFS_1(int x, int f) {
    fa[x] = f;
    d[x] = d[f] + 1;
    pos2[x] = ++num2;
    ST[num2][0] = x;
    for(int i = e[x]; i; i = edge[i].nex) {
        int y = edge[i].v;
        if(y == f) {
            continue;
        }
        DFS_1(y, x);
        ST[++num2][0] = x;
    }
    return;
}

inline void prework() {
    for(int i = 2; i <= num2; i++) pw[i] = pw[i >> 1] + 1;
    for(int j = 1; j <= pw[num2]; j++) {
        for(int i = 1; i + (1 << j) - 1 <= num2; i++) {
            if(d[ST[i][j - 1]] < d[ST[i + (1 << (j - 1))][j - 1]])
                ST[i][j] = ST[i][j - 1];
            else
                ST[i][j] = ST[i + (1 << (j - 1))][j - 1];
        }
    }
    return;
}

inline int lca(int x, int y) {
    x = pos2[x];
    y = pos2[y];
    if(x > y) std::swap(x, y);
    int t = pw[y - x + 1];
    if(d[ST[x][t]] < d[ST[y - (1 << t) + 1][t]])
        return ST[x][t];
    else
        return ST[y - (1 << t) + 1][t];
}

inline bool cmp(const int &a, const int &b) {
    return pos2[a] < pos2[b];
}

inline void work(int x) {
    if(use[x] != Time) {
        use[x] = Time;
        f[x] = 0;
        E[x] = 0;
    }
    return;
}

inline void build_t() {
    std::sort(imp + 1, imp + K + 1, cmp);
    TP = top = 0;
    work(imp[1]);
    stk[++top] = imp[1];
    for(int i = 2; i <= K; i++) {
        int x = imp[i], y = lca(x, stk[top]);
        work(x); work(y);
        while(top > 1 && pos2[y] <= pos2[stk[top - 1]]) {
            ADD(stk[top - 1], stk[top]);
            top--;
        }
        if(y != stk[top]) {
            ADD(y, stk[top]);
            stk[top] = y;
        }
        stk[++top] = x;
    }
    while(top > 1) {
        ADD(stk[top - 1], stk[top]);
        top--;
    }
    RT = stk[top];
    return;
}

void DFS(int x) {
    int a = 0, b = 0;
    for(int i = E[x]; i; i = EDGE[i].nex) {
        int y = EDGE[i].v;
        DFS(y);
        if(EDGE[i].len > 1) continue;
        if(f[y] > a) {
            b = a;
            a = f[y];
        }
        else b = std::max(b, f[y]);
    }
    if(vis[x] == Time) {
        ans = std::max(ans, a + b + 1);
        f[x] = a + 1;
    }
    return;
}

int main() {
    getp(N - 1);
    memset(vis, 0, sizeof(vis));
    int tot = top, flag = 1;

    scanf("%d", &n);
    for(int i = 1; i <= n; i++) {
        scanf("%d", &val[i]);
        int x = val[i];
        if(x > 1) flag = 0;
        while(x > 1) {
            int y = last[x];
            while(x % y == 0) {
                x /= y;
            }
            v[id[y]].push_back(i);
        }
    }
    for(int i = 1, x, y; i < n; i++) {
        scanf("%d%d", &x, &y);
        add(x, y); add(y, x);
    }

    if(flag) {
        puts("0");
        return 0;
    }

    DFS_1(1, 0);
    prework();

    for(int i = 1; i <= tot; i++) {
        K = 0;
        ++Time;
        for(int j = 0; j < (int)v[i].size(); j++) {
            imp[++K] = v[i][j];
            vis[v[i][j]] = Time;
        }
        build_t();
        DFS(RT);
    }

    printf("%d 
", ans);
    return 0;
}

G：题意：给定序列，你要把它分成尽可能多的几段，每段的权值是异或和。

要求没有哪些段的权值异或和为0。输出最大段数。无解-1。

解：考虑无解，肯定是总异或和为0。否则一定存在解。

发现这个东西，其实等价于选出一些前缀，因为异或可以抵消，所以这些前缀能表示出的和这些段能表示出的是相同的。

然后就把前缀插入线性基，看能插入多少个。

看到异或就要想线性基。

#include <bits/stdc++.h>

const int N = 200010;

int b[32], a[N];

inline int insert(int x) {
    for(int i = 30; i >= 0 && x; i--) {
        if(((x >> i) & 1) == 0) continue;
        if(b[i]) x ^= b[i];
        else {
            b[i] = x;
            return 1;
        }
    }
    return 0;
}

int main() {

    int n;
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        a[i] ^= a[i - 1];
    }

    if(!a[n]) {
        printf("-1
");
        return 0;
    }

    int cnt = 0;
    for(int i = n; i >= 1; i--) {
        cnt += insert(a[i]);
    }

    printf("%d 
", cnt);
    return 0;
}