牛客练习赛88D题题解

本来以为是卡我询问，最后发现是卡了我的并查集...

题解：整个题目思路很清晰。所谓最小生成树实质上就是由输入的边生成的，直接上kruscal算法就好。
后面要在最小生成树上找两点间路径最大的边，可以直接用树链剖分+线段树来做，也就是边权变点权再lca即可（这个可以借鉴这个类型的模板“月下毛景树”）。
复杂度分析：因为这个题目的q比较大(1e7级别)，所以复杂度主要取决于后面的询问O(qlgn)并不错，但其实这里还是有点卡常(这时极限数据速度大概在7s左右)，所以要加一些优化，比如记录下来任意一点跳到树剖对应链top的最长边。
但这样在我本地跑极限数据还是在4s多一些，最后试着把kruscal算法中的并查集加上按秩合并，极限数据的时间就稳定在3s以内了。
后记：大佬们应该会有O(1)查询的方法吧，所以我这应该是最笨蛋最简单的暴力算法了吧。。。

代码：
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#define lson rec<<1,l,mid
#define rson rec<<1|1,mid+1,r
#define ull unsigned long long
#define ll long long
using namespace std;
const int maxn=100005,maxm=500005;
int n,m,fa,fb,cnt;
int zu[maxn],dep[maxn],sz[maxn],son[maxn],
    pos[maxn],poi[maxn],top[maxn],po[maxn];
int tr[maxm],num[maxn],vis[maxn],h[maxn];
struct nd{
    int x,y,w;
    bool operator<(const nd &p)
    const{
        return w<p.w;
    }
}lu[maxm];
struct node{
    int y,next,w;
}rd[maxn<<1];

inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch>'9'||ch<'0'){if(ch=='-') f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-48;ch=getchar();}
    return x*f;
}
inline ull readull()
{
    ull x=0,f=1;char ch=getchar();
    while(ch>'9'||ch<'0'){if(ch=='-') f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-48;ch=getchar();}
    return x*f;
}
int father(int u)
{
    if(zu[u]!=u) zu[u]=father(zu[u]);
    return zu[u];
}
inline void add(int u,int v,int w)
{
    rd[++cnt].y=v;rd[cnt].w=w;
    rd[cnt].next=num[u];num[u]=cnt;
}
void build(int u)
{
    int v;dep[u]=dep[zu[u]]+1;sz[u]=1;
    for(int i=num[u];i;i=rd[i].next){
        v=rd[i].y;if(zu[u]==v) continue;
        zu[v]=u;build(v);sz[u]+=sz[v];
        po[v]=rd[i].w;
        if(sz[v]>sz[son[u]]) son[u]=v;
    }
}
void dfs(int u)
{
    pos[u]=++cnt;poi[cnt]=u;int v;
    if(son[u]) top[son[u]]=top[u],dfs(son[u]);
    for(int i=num[u];i;i=rd[i].next){
        v=rd[i].y;if(v==zu[u]||v==son[u]) continue;
        top[v]=v;dfs(v);
    }
}
void built(int rec,int l,int r)
{
    if(l==r){
        tr[rec]=po[poi[l]];return;
    }
    int mid=(l+r)>>1;
    built(lson);built(rson);
    tr[rec]=max(tr[rec<<1],tr[rec<<1|1]);
}
ull myRand(ull &k1, ull &k2){
    ull k3 = k1, k4 = k2;
    k1 = k4;
    k3 ^= (k3 <<23);
    k2 = k3 ^ k4 ^ (k3 >>17) ^ (k4 >>26);
    return k2 + k4;
}
int query(int rec,int l,int r)
{
    if(fa<=l&&r<=fb) return tr[rec];
    int mid=(l+r)>>1;
    if(fa>mid) return query(rson);
    else if(fb<=mid) return query(lson);
    return max(query(lson),query(rson));
}
inline int aquery(int a,int b)
{
    int res=0;
    while(top[a]!=top[b]){
        if(dep[top[a]]<dep[top[b]]) swap(a,b);
        if(!vis[a]){
            fa=pos[top[a]];fb=pos[a];vis[a]=query(1,1,n);
        }
        res=max(res,vis[a]);
        a=zu[top[a]];
    }
    if(a!=b){
        if(dep[a]>dep[b]) swap(a,b);
        fa=pos[a]+1;fb=pos[b];
        res=max(res,query(1,1,n));
    }
    return res;
}
int main()
{
    //freopen("D.in","r",stdin);
    //freopen("D.out","w",stdout);
    n=read();m=read();
    for(int i=1;i<=m;++i){
        lu[i].x=read();lu[i].y=read();lu[i].w=read();
    }
    sort(lu+1,lu+1+m);int k=1,u,v,w;
    for(int i=1;i<=n;++i) zu[i]=i,h[i]=1;
    for(int i=1;i<=m;++i){
        u=father(lu[i].x);v=father(lu[i].y);
        if(u!=v){
            if(h[u]<h[v]) swap(u,v);
            zu[v]=u;h[u]+=h[v];
            w=lu[i].w;add(u,v,w);add(v,u,w);
            ++k;if(k==n) break;
        }
    }
    memset(zu,0,sizeof(zu));top[1]=1;
    build(1);cnt=0;dfs(1);built(1,1,n);
    int q,ans=0;
    ull ka,kb;
    q=read();ka=readull();kb=readull();
    for(int i=1;i<=q;++i){
        u=myRand(ka,kb)%n+1;
        v=myRand(ka,kb)%n+1;
        ans^=aquery(u,v);
    }
    printf("%d",ans);
    return 0;
}