牛客练习赛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; }