求助,树链剖分样例可过,全WA
查看原帖
求助,树链剖分样例可过,全WA
142110
yu__xuan楼主2020/4/29 21:54

调不出来了,求大佬帮忙找一下错误。

#include<cstdio>
#include<cstring>
#include<string>
#include<iostream>
#include<algorithm>
#define MAXN 100001

inline void read(int &T) {
	int x=0;bool f=0;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')f=!f;c=getchar();}
	while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
	T=f?-x:x;
}

int n,wt[MAXN],size[MAXN],dfn[MAXN],pre[MAXN];

namespace Seg {
	#define lson now<<1
	#define rson now<<1|1
	struct Node {
		int l,r,w;
	}tree[MAXN<<2];
	void build(int l,int r,int now) {
		tree[now].l=l,tree[now].r=r;
		if(tree[now].l==tree[now].r) {
			tree[now].w=wt[pre[l]];
			return;
		}
		int mid=(tree[now].l+tree[now].r)>>1;
		build(l,mid,lson),build(mid+1,r,rson);
		tree[now].w=tree[lson].w^tree[rson].w;
	}
	int query(int x,int y,int now) {
		if(tree[now].l>=x&&tree[now].r<=y) return tree[now].w;
		int mid=(tree[now].l+tree[now].r)>>1,ans=0;
		if(x<=mid) ans^=query(x,y,lson);
		if(y>mid) ans^=query(x,y,rson);
		return ans;
	}
}

namespace Cut {
	int fa[MAXN],dep[MAXN],son[MAXN];
	int cnt,pthn,head[MAXN],top[MAXN];
	struct Edge {
		int next,to,w;
	}pth[MAXN<<1];
	void add(int from,int to,int w) {
		pth[++pthn].to=to,pth[pthn].next=head[from];
		pth[pthn].w=w,head[from]=pthn;
	}
	void dfs1(int u,int father) {
		dep[u]=dep[father]+1,fa[u]=father,size[u]=1;
		for(int i=head[u];i;i=pth[i].next) {
			int x=pth[i].to;
			if(x!=father) {
				dfs1(x,u);
				wt[x]=pth[i].w;
				size[u]+=size[x];
				if(size[son[u]]<size[x]) son[u]=x;
			}
		}
	}
	void dfs2(int u,int tp) {
		top[u]=tp,dfn[u]=++cnt,pre[cnt]=u;
		if(son[u]) dfs2(son[u],tp);
		for(int i=head[u];i;i=pth[i].next) {
			int x=pth[i].to;
			if(x!=fa[u]&&x!=son[u]) dfs2(x,x);
		}
	}
	int ask(int x,int y) {
		int ans=0;
		while(top[x]!=top[y]) {
			if(dfn[top[x]]<dfn[top[y]]) std::swap(x,y);
			ans^=Seg::query(dfn[top[x]],dfn[x],1);
			x=fa[top[x]];
		}
		if(x==y) return ans;
		if(dep[x]>dep[y]) std::swap(x,y);
		ans^=Seg::query(dfn[x],dfn[y],1);
		return ans;
	}
}

int main() {
	read(n);
	for(int i=1,u,v,w;i<n;++i) {
		read(u),read(v),read(w);
		Cut::add(u,v,w);Cut::add(v,u,w);
	}
	Cut::dfs1(1,1),Cut::dfs2(1,1),Seg::build(1,n,1);
	int q;read(q);
	for(int i=1,u,v;i<=q;++i) {
		read(u),read(v);
		printf("%d\n",Cut::ask(u,v));
	}
	return 0;
}
2020/4/29 21:54
加载中...