题解：P9295 [POI 2020] Gang Biciaków / 布茨帮

zzzyyyyhhhhh · 2025-02-03 10:42:00 · 题解

感觉此解法不是正解，需要大力卡常才能通过。

树上数颜色想到树分块（设置关键点的那种）。维护到每个关键点每种颜色的出现次数和根到每个关键点的颜色数，查询时暴力向上跳到最近的一个关键点，用关键点的颜色数加上路径上未在根到关键点路径上出现过的颜色数，修改时修改影响到的关键点的颜色数和颜色种类即可。

代码。

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e5+100,M = 1.5e5+1;
namespace  rorrurorror
{
    const int MAXBUF=1<<20;
    char buf[MAXBUF],*p1=buf,*p2=buf;
    char pbuf[MAXBUF],*pp=pbuf;
    inline char getc(){return (p1==p2)&&(p2=(p1=buf)+fread(buf,1,MAXBUF,stdin),p1==p2)?EOF:*p1++;}
    inline void ri(int &x){x=0;char c=getc();while(!isdigit(c))c=getc();while(isdigit(c))x=x*10+(c^48),c=getc();}
    inline void putc(char c){(pp==pbuf+MAXBUF)&&(fwrite(pbuf,1,MAXBUF,stdout),pp=pbuf),*pp++=c;}
    inline void print_final(){fwrite(pbuf,1,pp-pbuf,stdout),pp=pbuf;}
    inline void wi(int x){if(x>9)wi(x/10);putc(x%10^48);}
}
using rorrurorror::ri;
using rorrurorror::wi;
using rorrurorror::getc;
using rorrurorror::putc;
using rorrurorror::print_final;
struct edge{int t,w,pos;};
vector<edge> a[N];
int n,m,qq;
bool key[N],tt[M];
int cnttmp[M],dep[N],mxdep[N],f[N];
int blo,cnt[300][M],ans[N],tot,be[N],rb[N],bg[N],ke[N],ed[N],to[N];
int tmp[N];
inline void dfs0(int x,int fa)
{
    mxdep[x]=dep[x];
    edge i;
    for(int j=0;j<a[x].size();j++)
    {
        i=a[x][j];
        if(i.t==fa)continue;
        f[i.t]=x;
        to[i.t]=i.w;
        ke[i.pos]=i.t;
        dep[i.t]=dep[x]+1;
        dfs0(i.t,x);
        mxdep[x]=max(mxdep[x],mxdep[i.t]);
    }
    if(dep[x]%blo==0&&mxdep[x]-dep[x]>=blo)key[x]=1;
}
inline void dfs(int x,int fa)
{
    bg[x]=tot+1;
    if(key[x])memcpy(cnt[be[x]=++tot],cnttmp,sizeof(int)*(m+1)),rb[tot]=x;
    edge i;
    for(int j=0;j<a[x].size();j++)
    {
        i=a[x][j];
        if(i.t==fa)continue;
        cnttmp[i.w]++;
        ans[i.t]=ans[x];
        if(cnttmp[i.w]==1)ans[i.t]++;
        dfs(i.t,x);
        cnttmp[i.w]--;
    }
    ed[x]=tot;
}
inline int get(int x)
{
    tot=0;
    while(!key[x])
    {
        if(!tt[to[x]])tmp[++tot]=to[x],tt[to[x]]=1;
        x=f[x];
    }
    int res=ans[x];
    for(int i=1;i<=tot;i++)
    {
        if(!cnt[be[x]][tmp[i]])res++;
        tt[tmp[i]]=0;
    }
    return res;
}
inline void ea(int x,int tp)
{
    for(int i=bg[x];i<=ed[x];i++)
    {
        cnt[i][tp]--;
        if(!cnt[i][tp])ans[rb[i]]--;
    }
}
inline void ad(int x,int tp)
{
    for(int i=bg[x];i<=ed[x];i++)
    {
        cnt[i][tp]++;
        if(cnt[i][tp]==1)ans[rb[i]]++;
    }
}
signed main()
{
    ri(n),ri(m),ri(qq);
    blo=sqrt(n)*1.21+1;
    int x,y,z;
    char op;
    for(int i=1;i<n;i++)ri(x),ri(y),ri(z),a[x].push_back({y,z,i}),a[y].push_back({x,z,i});
    dfs0(1,0);
    key[1]=1;
    dfs(1,0);
    while(qq--)
    {
        op=getc();
        while(op!='Z'&&op!='B')op=getc();
        if(op=='Z')
        {
            ri(x);
            get(x);
            wi(get(x)),putc('\n');
        }
        else
        {
            ri(x),ri(y);
            if(y==to[ke[x]])continue;
            ea(ke[x],to[ke[x]]);
            to[ke[x]]=y;
            ad(ke[x],to[ke[x]]);
        }
    }
    print_final();
}