社区讨论

萌新求助简单题,30行代码都出错,求教

P2486[SDOI2011] 染色参与者 4已保存回复 14

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
14 条
当前快照
1 份
快照标识符
@mi7yw0ta
此快照首次捕获于
2025/11/21 05:52
4 个月前
此快照最后确认于
2025/11/21 06:46
4 个月前
查看原帖
题目是吸引你点进来的,都进来了,就帮忙看看吧(雾)
树剖:Dfs和线段树应该没锅,就是判区间做优的时候可能出了问题,过不去样例
CPP
#include <bits/stdc++.h>

using namespace std;
#define int long long
int n,m;
int a[100005];
struct Node
{
    int v;
    Node *next;
}*h[100005],pool[200005];
struct SGTree
{
    int le,ri;
    int lc,rc;
    int la;
    int sum;
}t[400005];
int top[100005];
int son[100005];
int size[100005];
int w[100005];
int rw[100005];
int dep[100005];
int f[100005];
int cnt=0,tot=0;
void Adde(int u,int v)
{
    Node *p=&pool[++tot];
    p->v=v;
    p->next=h[u];
    h[u]=p;
}
void Dfs1(int u,int fa)
{
    int maxsize=-1,maxson=0;
    size[u]=1;
    f[u]=fa;
    for(Node *p=h[u];p;p=p->next)
    {
        if(p->v!=fa)
        {
            dep[p->v]=dep[u]+1;
            Dfs1(p->v,u);
            if(maxsize<size[p->v])
            {
                maxsize=size[p->v];
                maxson=p->v;
            }
            size[u]+=size[p->v];
        }
    }
    son[u]=maxson;
}
void Dfs2(int u,int fa)
{
    cnt++;
    w[u]=cnt;
    if(son[u])
    {
        top[son[u]]=top[u];
        Dfs2(son[u],fa);
    }	
    for(Node *p=h[u];p;p=p->next)
    {
        if(p->v!=f[u]&&p->v!=son[u])
        {
            top[p->v]=p->v;
            Dfs2(p->v,p->v);
        }
    }
}
void BuildT(int id,int l,int r)
{
	t[id].le=l;
	t[id].ri=r;
	t[id].lc=a[rw[l]];
	t[id].rc=a[rw[r]];
	t[id].la=0;
	if(l==r)
	{
		t[id].sum=1;
		return;
	}
	int Mid=(l+r)/2;
	BuildT(id*2,l,Mid);
	BuildT(id*2+1,Mid+1,r);
	t[id].sum=t[id*2].sum+t[id*2+1].sum;
	if(t[id*2].lc==t[id*2+1].rc)
	{
		t[id].sum--;
	}
}
void Push(int id)
{
	if(t[id].la)
	{
		t[id*2].la=t[id].la;
		t[id*2+1].la=t[id].la;
		t[id].sum=1;
		t[id].lc=t[id].la;
		t[id].rc=t[id].la;
		t[id].la=0;
	}
}
void Change(int id,int l,int r,int c)
{
	if(t[id].le==l&&t[id].ri==r)
	{
		t[id].la=c;
		return;
	}
	Push(id);
	if(t[id*2].ri>=r)
	{
		Change(id*2,l,r,c);
	}
	else if(t[id*2+1].le<=l)
	{
		Change(id*2+1,l,r,c);
	}
	else
	{
		Change(id*2,l,t[id*2].ri,c);
		Change(id*2+1,t[id*2+1].le,r,c);
	}
	t[id].sum=t[id*2].sum+t[id*2+1].sum;
	if(t[id*2].rc==t[id*2+1].lc)
	{
		t[id].sum--;
	}
}
int Query(int id,int l,int r)
{
	if(t[id].le==l&&t[id].ri==r)
	{
		return t[id].sum;
	}
	Push(id);
	if(t[id*2].ri>=r)
	{
		return Query(id*2,l,r);
	}
	else if(t[id*2+1].le<=l)
	{
		return Query(id*2+1,l,r);
	}
	else
	{
		int ans=Query(id*2,l,t[id*2].ri)+Query(id*2+1,t[id*2+1].le,r);
		if(t[id*2].rc==t[id*2+1].lc)
		{
			ans--;
		}
		return ans;
	}
} 
int Modify(int x,int y,int c)
{
    while(top[x]!=top[y])
    {
        if(dep[top[x]]<dep[top[y]])
        {
            swap(x,y);
        }
        Change(1,w[top[x]],w[x],c);
        x=f[top[x]];
    }
    if(w[x]>w[y])
    {
        swap(x,y);
    }
    Change(1,w[x],w[y],c);
}
int Ask(int x,int y)
{
//	cout << "in" <<endl;
    int res=0;
    while(top[x]!=top[y])
    {
//    	printf("%lld %lld\n",x,y);
        if(dep[top[x]]<dep[top[y]])
        {
            swap(x,y);
        }
        res+=Query(1,w[top[x]],w[x]);
        if(t[w[top[x]]].rc==t[w[f[top[x]]]].lc)
        {
        	res--;
        }
        x=f[top[x]];
//        printf("%lld\n",res);
    }
//    cout << "s" <<endl;
    if(w[x]>w[y])
    {
        swap(x,y);
    }
    res+=Query(1,w[x],w[y]);
    return res;
}

signed main()
{
	scanf("%lld%lld",&n,&m);
	for(int i=1;i<=n;++i)
	{
		scanf("%lld",&a[i]);
	}
	int uu,vv;
	for(int i=1;i<n;++i)
	{
		scanf("%lld%lld",&uu,&vv);
		Adde(uu,vv);
		Adde(vv,uu);
	}
	Dfs1(1,0);
	Dfs2(1,1);
	for(int i=1;i<=n;++i)
	{
		if(top[i]==0)
		{
			top[i]=i;
		}
	}
	for(int i=1;i<=n;++i)
	{
		rw[w[i]]=i;
	}
	BuildT(1,1,n);
//	for(int i=1;i<=4*n;++i)
//	{
//		printf("%lld %lld %lld %lld %lld\n",t[i].le,t[i].ri,t[i].lc,t[i].rc,t[i].sum);
//	}
//	for(int i=1;i<=n;++i)
//	{
//		printf("%lld %lld %lld %lld\n",top[i],dep[i],w[i],size[i]);
//	}
	char op;
	int x,y,z;
	while(m--)
	{
		cin >> op;
		scanf("%lld%lld",&x,&y);
		if(op=='Q')
		{
			printf("%lld\n",Ask(x,y));
		}
		else
		{
			scanf("%lld",&z);
			Modify(x,y,z);
		}
	}
	return 0;
}

回复

14 条回复,欢迎继续交流。

正在加载回复...