树剖全WA求调
查看原帖
树剖全WA求调
121813
老子是北瓜楼主2022/7/25 19:28
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<cassert>
#define line cout<<endl;
#define ran for(int i=1; i<=n; ++i)
#define ll long long
#define ull unsigned long long
#define dbg cout<<"ok"<<endl;
#define mod
#define N 100050
#define lson p<<1
#define rson p<<1|1

using namespace std;

int n,m,cnt,c[N],b[N],len;
int fa[N],son[N],sz[N],top[N],dfn[N],d[N];
vector<int> g[N];
struct tree { int l,r,lc,rc,sum,tag; } t[N*4];
struct seg { int lc,rc,res; } ;

void dfs1(int u,int f)
{
	fa[u] = f;
	sz[u] = 1;
	d[u] = d[f] + 1;
	for(int v:g[u])
	{
		if(v==f) continue;
		dfs1(v,u);
		sz[u] += sz[v];
		if(sz[v] > sz[son[u]])
			son[u] = v;
	}
}

void dfs2(int u,int f)
{
	dfn[u] = ++cnt;
	b[dfn[u]] = c[u];
	top[u] = f;
	if(son[u] == 0) return;
	dfs2(son[u],f);
	
	for(int v:g[u])
		if(v != fa[u] && v != son[u])
			dfs2(v,v);
}

void build(int p,int l,int r){
	t[p].l = l; t[p].r = r; t[p].tag = 0;
	if(l == r) {
		t[p].lc = t[p].rc = b[l];
		t[p].sum = 1;
		return ;
	}
	int mid = (l+r) >> 1;
	build(lson,l,mid);
	build(rson,mid+1,r);
	t[p].lc = t[lson].lc;
	t[p].rc = t[rson].rc;
	t[p].sum = t[lson].sum + t[rson].sum - (t[lson].rc == t[rson].lc);
}

void push_down(int p) {
	int tg = t[p].tag;
	
	if(tg == 0) return ;
	t[lson].tag = t[rson].tag = tg;
	t[lson].sum = t[rson].sum = 1;
	t[lson].lc = t[rson].lc = tg;
	t[lson].rc = t[rson].rc = tg;
	t[p].tag = 0;
}

void modify(int p,int l,int r,int val) {
	if(l <= t[p].l && t[p].r <= r) {
		t[p].tag = t[p].lc = t[p].rc = val;
		t[p].sum = 1;
		return ;
	}
	push_down(p);
	int mid = (t[p].l + t[p].r) >> 1;
	if(l <= mid) modify(lson,l,r,val);
	if(r > mid) modify(rson,l,r,val);
	t[p].lc = t[lson].lc;
	t[p].rc = t[rson].rc;
	t[p].sum = t[lson].sum + t[rson].sum - (t[lson].rc == t[rson].lc);
}

seg query(int p,int l,int r) {
	if(l <= t[p].l && t[p].r <= r) return {t[p].lc, t[p].rc, t[p].sum};
	
	push_down(p);
	int mid = (t[p].l + t[p].r) >> 1;
	
	seg left,right,all;
	if(l <= mid) left = query(lson,l,r);
	if(r > mid) right = query(rson,l,r);
	
	if(r <= mid) return left;
	if(l > mid) return right;
	
	all.lc = left.lc;
	all.rc = right.lc;
	all.res = left.res + right.res - (left.rc == right.lc);
	return all;
}

void change(int u,int v,int col) {
	while(top[u] != top[v]) 
	{
		if(d[top[u]] < d[top[v]]) swap(u,v);
		modify(1, dfn[top[u]], dfn[u], col);
		u = fa[top[u]];
	}
	if(dfn[u] > dfn[v]) swap(u,v);
	modify(1, dfn[u], dfn[v], col);
}

int ask(int u,int v){
	int ans = 0, cu = 0, cv = 0;
	seg tmp;
	
	while(top[u] != top[v]) 
	{
		if(d[top[u]] < d[top[v]]) swap(u,v), swap(cu, cv);
		
		tmp = query(1, dfn[top[u]], dfn[u]);
		ans += tmp.res - (cu == tmp.rc);
		cu = tmp.lc;
//		cout<<u<<" "<<top[u]<<"  "<<dfn[top[u]]<<" "<<dfn[u]<<" "<<tmp.lc<<" "<<tmp.rc<<" "<<tmp.res<<endl;
		u = fa[top[u]];
	}
	
//	if(dfn[u] > dfn[v]) swap(u,v), swap(cu, cv);
//	tmp = query(1, dfn[u], dfn[v]);
//	ans += tmp.res - (cu == tmp.lc) - (cv == tmp.rc);
	
	if(dfn[u] < dfn[v]) swap(u,v), swap(cu,cv);
	tmp = query(1,dfn[v],dfn[u]);
	ans += tmp.res ;
	if(tmp.rc == cu) --ans;
	if(tmp.lc == cv) --ans;
//	cout<<dfn[top[u]]<<" "<<dfn[u]<<" "<<tmp.lc<<" "<<tmp.rc<<" "<<tmp.res<<endl;
//	cout<<cu<<" "<<cv<<endl;
	return ans;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
	
	cin>>n>>m;
	for(int i=1; i<=n; ++i) cin>>c[i];
	
	for(int i=1; i<n; ++i)
	{
		int x,y;
		cin>>x>>y;
		g[x].push_back(y);
		g[y].push_back(x);
	}
	
	dfs1(1,0);
	dfs2(1,1);
	build(1,1,n);
	
	while(m--)
	{
		char opt;
		int x,y,col;
		
		cin>>opt;
		
		if(opt=='Q')
		{
			cin>>x>>y;
			cout<<ask(x,y)<<endl;
		}
		else
		{
			cin>>x>>y>>col;
			change(x,y,col);
		}
	}
	
    return 0;
}

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<cassert>
#define line cout<<endl;
#define ran for(int i=1; i<=n; ++i)
#define ll long long
#define ull unsigned long long
#define dbg cout<<"ok"<<endl;
#define mod
#define N 100050
#define lson p<<1
#define rson p<<1|1

using namespace std;

int n,m,cnt,c[N],b[N],len;
int fa[N],son[N],sz[N],top[N],dfn[N],d[N];
vector<int> g[N];
struct tree { int l,r,lc,rc,sum,tag; } t[N*4];
struct seg { int lc,rc,res; } ;

void dfs1(int u,int f)
{
	fa[u] = f;
	sz[u] = 1;
	d[u] = d[f] + 1;
	for(int v:g[u])
	{
		if(v==f) continue;
		dfs1(v,u);
		sz[u] += sz[v];
		if(sz[v] > sz[son[u]])
			son[u] = v;
	}
}

void dfs2(int u,int f)
{
	dfn[u] = ++cnt;
	b[dfn[u]] = c[u];
	top[u] = f;
	if(son[u] == 0) return;
	dfs2(son[u],f);
	
	for(int v:g[u])
		if(v != fa[u] && v != son[u])
			dfs2(v,v);
}

void build(int p,int l,int r){
	t[p].l = l; t[p].r = r; t[p].tag = 0;
	if(l == r) {
		t[p].lc = t[p].rc = b[l];
		t[p].sum = 1;
		return ;
	}
	int mid = (l+r) >> 1;
	build(lson,l,mid);
	build(rson,mid+1,r);
	t[p].lc = t[lson].lc;
	t[p].rc = t[rson].rc;
	t[p].sum = t[lson].sum + t[rson].sum - (t[lson].rc == t[rson].lc);
}

void push_down(int p) {
	int tg = t[p].tag;
	
	if(tg == 0) return ;
	t[lson].tag = t[rson].tag = tg;
	t[lson].sum = t[rson].sum = 1;
	t[lson].lc = t[rson].lc = tg;
	t[lson].rc = t[rson].rc = tg;
	t[p].tag = 0;
}

void modify(int p,int l,int r,int val) {
	if(l <= t[p].l && t[p].r <= r) {
		t[p].tag = t[p].lc = t[p].rc = val;
		t[p].sum = 1;
		return ;
	}
	push_down(p);
	int mid = (t[p].l + t[p].r) >> 1;
	if(l <= mid) modify(lson,l,r,val);
	if(r > mid) modify(rson,l,r,val);
	t[p].lc = t[lson].lc;
	t[p].rc = t[rson].rc;
	t[p].sum = t[lson].sum + t[rson].sum - (t[lson].rc == t[rson].lc);
}

seg query(int p,int l,int r) {
	if(l <= t[p].l && t[p].r <= r) return {t[p].lc, t[p].rc, t[p].sum};
	
	push_down(p);
	int mid = (t[p].l + t[p].r) >> 1;
	
	seg left,right,all;
	if(l <= mid) left = query(lson,l,r);
	if(r > mid) right = query(rson,l,r);
	
	if(r <= mid) return left;
	if(l > mid) return right;
	
	all.lc = left.lc;
	all.rc = right.lc;
	all.res = left.res + right.res - (left.rc == right.lc);
	return all;
}

void change(int u,int v,int col) {
	while(top[u] != top[v]) 
	{
		if(d[top[u]] < d[top[v]]) swap(u,v);
		modify(1, dfn[top[u]], dfn[u], col);
		u = fa[top[u]];
	}
	if(dfn[u] > dfn[v]) swap(u,v);
	modify(1, dfn[u], dfn[v], col);
}

int ask(int u,int v){
	int ans = 0, cu = 0, cv = 0;
	seg tmp;
	
	while(top[u] != top[v]) 
	{
		if(d[top[u]] < d[top[v]]) swap(u,v), swap(cu, cv);
		
		tmp = query(1, dfn[top[u]], dfn[u]);
		ans += tmp.res - (cu == tmp.rc);
		cu = tmp.lc;
//		cout<<u<<" "<<top[u]<<"  "<<dfn[top[u]]<<" "<<dfn[u]<<" "<<tmp.lc<<" "<<tmp.rc<<" "<<tmp.res<<endl;
		u = fa[top[u]];
	}
	
//	if(dfn[u] > dfn[v]) swap(u,v), swap(cu, cv);
//	tmp = query(1, dfn[u], dfn[v]);
//	ans += tmp.res - (cu == tmp.lc) - (cv == tmp.rc);
	
	if(dfn[u] < dfn[v]) swap(u,v), swap(cu,cv);
	tmp = query(1,dfn[v],dfn[u]);
	ans += tmp.res ;
	if(tmp.rc == cu) --ans;
	if(tmp.lc == cv) --ans;
//	cout<<dfn[top[u]]<<" "<<dfn[u]<<" "<<tmp.lc<<" "<<tmp.rc<<" "<<tmp.res<<endl;
//	cout<<cu<<" "<<cv<<endl;
	return ans;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
	
	cin>>n>>m;
	for(int i=1; i<=n; ++i) cin>>c[i];
	
	for(int i=1; i<n; ++i)
	{
		int x,y;
		cin>>x>>y;
		g[x].push_back(y);
		g[y].push_back(x);
	}
	
	dfs1(1,0);
	dfs2(1,1);
	build(1,1,n);
	
	while(m--)
	{
		char opt;
		int x,y,col;
		
		cin>>opt;
		
		if(opt=='Q')
		{
			cin>>x>>y;
			cout<<ask(x,y)<<endl;
		}
		else
		{
			cin>>x>>y>>col;
			change(x,y,col);
		}
	}
	
    return 0;
}

RT，对着题解改了两个小时了，还是0蛋QAQ

2022/7/25 19:28