题解 树

本文主要是介绍题解 树，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

传送门

一开始想拆边，后来发现不用那么麻烦

如果给每个被染成白色的点打一个被染色的时间戳
那么可以发现一条边是白色的充分必要条件是它的两个端点时间戳相同
于是转化成了染色这道题，树剖即可

Code:

#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define N 300010
#define ll long long 
//#define int long long 

char buf[1<<21], *p1=buf, *p2=buf;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf, 1, 1<<21, stdin)), p1==p2?EOF:*p1++)
inline int read() {
	int ans=0, f=1; char c=getchar();
	while (!isdigit(c)) {if (c=='-') f=-f; c=getchar();}
	while (isdigit(c)) {ans=(ans<<3)+(ans<<1)+(c^48); c=getchar();}
	return ans*f;
}

int n, q;
int head[N], size=1;
struct edge{int to, next;}e[N<<1];
inline void add(int s, int t) {e[++size].to=t; e[size].next=head[s]; head[s]=size;}

namespace force{
	int val[N<<1];
	bool dfs(int u, int to, int fa) {
		if (u==to) {
			for (int i=head[u]; ~i; i=e[i].next)
				val[i]=val[i^1]=1;
			return 1;
		}
		for (int i=head[u],v; ~i; i=e[i].next) {
			v = e[i].to;
			if (v==fa) continue;
			if (dfs(v, to, u)) {
				for (int j=head[u]; ~j; j=e[j].next)
					val[j]=val[j^1]=1;
				val[i]=val[i^1]=0;
				return 1;
			}
		}
		return 0;
	}
	int query(int u, int to, int fa) {
		//cout<<"query "<<u<<' '<<to<<' '<<fa<<endl;
		if (u==to) return 1;
		for (int i=head[u],v; ~i; i=e[i].next) {
			v = e[i].to;
			if (v==fa) continue;
			int t=query(v, to, u);
			//cout<<"t: "<<t<<' '<<i<<' '<<val[i]<<endl;
			if (t) return t+val[i];
		}
		return 0;
	}
	void solve() {
		for (int i=1; i<=size; ++i) val[i]=1;
		q=read();
		for (int i=1,tp,x,y; i<=q; ++i) {
			tp=read(); x=read(); y=read();
			if (tp&1) {
				dfs(x, y, 0);
			}
			else {
				//cout<<"val: "; for (int i=1; i<=size; ++i) cout<<val[i]<<' '; cout<<endl;
				printf("%d\n", query(x, y, 0)-1);
			}
		}
		exit(0);
	}
}

namespace task1{
	int id[N], rk[N], siz[N], msiz[N], mson[N], dep[N], tot, fa[N], top[N];
	struct line{
		int l, r, cnt;
		line(){} line(int a, int b, int c):l(a),r(b),cnt(c){}
		inline void build(int a, int b, int c) {l=a, r=b, cnt=c;}
	};
	inline line operator + (line a, line b) {return line(a.l, b.r, a.cnt+b.cnt+(a.r!=b.l));}
	int tl[N<<2], tr[N<<2], tag[N<<2]; line dat[N<<2];
	#define tl(p) tl[p]
	#define tr(p) tr[p]
	#define tag(p) tag[p]
	#define dat(p) dat[p]
	#define pushup(p) dat(p)=dat(p<<1)+dat(p<<1|1)
	void spread(int p) {
		if (!tag(p)) return ;
		dat(p<<1).build(tag(p), tag(p), 0); tag(p<<1)=tag(p);
		dat(p<<1|1).build(tag(p), tag(p), 0); tag(p<<1|1)=tag(p);
		tag(p)=0;
	}
	void build(int p, int l, int r) {
		tl(p)=l; tr(p)=r;
		if (l==r) {dat(p).build(l, l, 0); return ;}
		int mid=(l+r)>>1;
		build(p<<1, l, mid);
		build(p<<1|1, mid+1, r);
		pushup(p);
	}
	void upd(int p, int l, int r, int tim) {
		if (l<=tl(p) && r>=tr(p)) {
			dat(p).build(tim, tim, 0);
			tag(p)=tim;
			return ;
		}
		spread(p);
		int mid=(tl(p)+tr(p))>>1;
		if (l<=mid) upd(p<<1, l, r, tim);
		if (r>mid) upd(p<<1|1, l, r, tim);
		pushup(p);
	}
	line query(int p, int l, int r) {
		if (l<=tl(p) && r>=tr(p)) return dat(p);
		spread(p);
		int mid=(tl(p)+tr(p))>>1;
		if (l<=mid && r>mid) return query(p<<1, l, r)+query(p<<1|1, l, r);
		if (l<=mid) return query(p<<1, l, r);
		if (r>mid) return query(p<<1|1, l, r);
		return line(-2, -2, -1);
	}
	void dfs1(int u, int pa) {
		siz[u]=1;
		for (int i=head[u],v; ~i; i=e[i].next) {
			v = e[i].to;
			if (v==pa) continue;
			dep[v]=dep[u]+1; fa[v]=u;
			dfs1(v, u);
			siz[u]+=siz[v];
			if (siz[v]>msiz[u]) msiz[u]=siz[v], mson[u]=v;
		}
	}
	void dfs2(int u, int f, int t) {
		top[u]=t;
		id[u]=++tot;
		//cout<<"id "<<u<<' '<<tot<<endl;
		rk[tot]=u;
		if (!mson[u]) return ;
		dfs2(mson[u], u, t);
		for (int i=head[u],v; ~i; i=e[i].next) {
			v = e[i].to;
			if (v!=mson[u] && v!=f)
				dfs2(v, u, v);
		}
	}
	void upd(int a, int b, int tim) {
		//cout<<"upd: "<<a<<' '<<b<<' '<<tim<<endl;
		while (top[a]!=top[b]) {
			if (dep[top[a]]<dep[top[b]]) swap(a, b);
			upd(1, id[top[a]], id[a], tim); //, cout<<"upd2: "<<id[top[a]]<<' '<<id[a]<<' '<<tim<<endl;
			a=fa[top[a]];
		}
		if (dep[a]>dep[b]) swap(a, b);
		upd(1, id[a], id[b], tim); //, cout<<"upd3: "<<id[a]<<' '<<id[b]<<' '<<tim<<endl;
	}
	int query(int a, int b) {
		//cout<<"query "<<a<<' '<<b<<endl;
		line t1(-1, -1, -1), t2(-1, -1, -1);
		while (top[a]!=top[b]) {
			if (dep[top[a]]<dep[top[b]]) swap(a, b), swap(t1, t2);
			//cout<<"while "<<a<<' '<<b<<endl;
			//line t=query(1, id[top[a]], id[a]);
			//cout<<"t1: "<<t1.l<<' '<<t1.r<<' '<<t1.cnt<<endl;
			//cout<<"t: "<<t.l<<' '<<t.r<<' '<<t.cnt<<endl;
			t1 = query(1, id[top[a]], id[a])+t1;
			//cout<<"now: "<<t1.l<<' '<<t1.r<<' '<<t1.cnt<<endl;
			a=fa[top[a]];
		}
		//cout<<"out: "<<a<<' '<<b<<endl;
		if (dep[a]>dep[b]) swap(a, b), swap(t1, t2);
		//line t=query(1, id[a], id[b]);
		//cout<<"t1: "<<t1.l<<' '<<t1.r<<' '<<t1.cnt<<endl;
		//cout<<"t2: "<<t2.l<<' '<<t2.r<<' '<<t2.cnt<<endl;
		//cout<<"t: "<<t.l<<' '<<t.r<<' '<<t.cnt<<endl;
		t2 = query(1, id[a], id[b])+t2;
		//cout<<"now: "<<t1.l<<' '<<t1.r<<' '<<t1.cnt<<endl;
		return t1.cnt+t2.cnt+(t1.l!=t2.l);
	}
	void solve() {
		q=read();
		dep[1]=1; dfs1(1, 0);
		dfs2(1, 0, 1);
		build(1, 1, tot);
		for (int i=1,tp,x,y; i<=q; ++i) {
			tp=read(); x=read(); y=read();
			//cout<<"tp: "<<tp<<endl;
			if (tp&1) {
				upd(x, y, i+n);
			}
			else {
				//cout<<"val: "; for (int i=1; i<=size; ++i) cout<<val[i]<<' '; cout<<endl;
				printf("%d\n", query(x, y));
			}
		}
		exit(0);
	}
}

signed main()
{
	memset(head, -1, sizeof(head));
	//bool chain=1;
	n=read();
	for (int i=1,u,v; i<n; ++i) {
		u=read(); v=read();
		add(u, v); add(v, u);
	}
	//if (n<=1000) force::solve();
	//else task1::solve();
	task1::solve();
	
	return 0;
}

这篇关于题解 树的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！