题目链接

bzoj4668: 冷战

题解

按秩合并并查集,每次增长都是小集合倍数的两倍以上,层数不超过logn

查询路径最大值

LCT同解

代码

#include<bits/stdc++.h>

using namespace std;

inline int read() {

    int x = 0,f = 1;

    char c = getchar();

    while(c < '0' || c > '9')c = getchar();

    while(c <= '9' && c >= '0')x = x * 10 + c - '0',c = getchar();

    return x * f; }

int n,m;

const int maxn = 5000007;

int cnt = 0 ,fa[maxn],deep[maxn],siz[maxn],v[maxn];

int find(int x)  {

    if(fa[x] != x) {

        int f = find(fa[x]);

        deep[x] = deep[fa[x]] + 1;

        return f;

    } else return x;

}

void Union(int x,int y,int C) {

    int f1 = find(x),f2 = find(y);

    if(f1 == f2) return ;

    if(siz[f1] > siz[f2]) fa[f2] = f1,v[f2] = C,siz[f1] += siz[f2];

    else fa[f1] = f2,v[f1] = C,siz[f2] += siz[f1];

}

int query(int x,int y) {

    int f1 = find(x),f2 = find(y);

    if(f1 != f2)return 0;

    int ret = 0 ;

    for(;x != y;) {

        if(deep[x] < deep[y]) swap(x,y);

        ret = max(ret,v[x]),x = fa[x];

    } return ret;

}

int main() {

    n = read(),m = read();

    for(int i = 1;i <= n;++ i) fa[i] = i,siz[i] = 1;

    int ans = 0;

    for(int op,u,v,i = 1;i <= m;++ i) {

        op = read();u = read() ^ ans,v = read() ^ ans;

        if(!op) {

            Union(u,v,++ cnt);

        } else printf("%d\n",ans = query(u,v));

    }

    return 0;

}