「POI2020 R1」Gang Biciaków 题解

· · 个人记录

题意：

有一棵 n 个点的树，每条边上有一个颜色

两个操作：

1、将某条边的颜色换为 x

2、查询 x 到根路径上有多少颜色

题解：

做法不少

解法1：树上带修莫队

注意到左端点始终为 1，所以复杂度严格二次根号

解法2：根号重构

每 \sqrt n 个操作重构一次

对于每个点，把还没有处理的询问用 vector 存下来，然后 dfs，按 dfs 序加入祖先的颜色，回来时撤销

在 u 号点，已经加入了祖先的颜色，再对于 u 的每个询问，执行存下来的时间在询问之前的修改，再撤回

时间复杂度 O(m \times \sqrt n)

代码（解法2）：

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#define ri register int
#define ll long long
#define fi first
#define se second
using namespace std;
const int Maxn=1e5;
const int Maxm=15e4; 
struct Node {
    int x,y,tim;
}save[Maxm+5];
vector<int>adj[Maxn+5];
int lt[Maxn+5],nt[Maxm+5],ed[Maxm+5],cnt_e;
int dep[Maxn+5],in[Maxn+5],out[Maxn+5],timer;
int col[Maxn+5],cnt[Maxm+5],sum;
int ans[Maxm+5];
int n,m,k,tot;
template<typename T> struct Fread {
    char buf[1<<20],*p1=buf,*p2=buf,obuf[1<<20],*p3=obuf;
    #define getchar() p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin),p1==p2)?EOF:*p1++
    #define putchar(x) (p3-obuf<(1<<20))?(*p3++=x):(fwrite(obuf,p3-obuf,1,stdout),p3=obuf,*p3++=x)
    inline T read() {
        T x=0;
        bool sgn=0;
        char c=getchar();
        while(c<'0'||c>'9') {
            if(c=='-')sgn=1;
            c=getchar();
        }
        while(c>='0'&&c<='9') {
            x=(x<<3)+(x<<1)+(c^48);
            c=getchar();
        }
        return sgn?-x:x;
    }
    inline char read_char() {
        char c=getchar();
        while(c<'A'||c>'Z') {
            c=getchar();
        }
        return c;
    }
    int stk[20];
    inline void print(auto x,char c) {
        if(x<0) {
            putchar('-'),x=-x;
        }
        int top=0;
        do {
            stk[++top]=x%10,x/=10;  
        }while(x);
        for(ri i=top;i>=1;i--)putchar(stk[i]+'0');
        putchar(c);
    }
    void write() {
        fwrite(obuf,p3-obuf,1,stdout);
    }
};
Fread<int>IO;
inline int read() {return IO.read();}
inline char read_char() {return IO.read_char();}
inline void print(auto x,auto c) {IO.print(x,c);}
inline void addedge(int x,int y) {
    ed[++cnt_e]=y;nt[cnt_e]=lt[x];lt[x]=cnt_e;
}
inline void add(int x) {
    ++cnt[x];
    if(cnt[x]==1)++sum;
}
inline void erase(int x) {
    --cnt[x];
    if(cnt[x]==0)--sum; 
}
void dfs(int u,int fa) {
    dep[u]=dep[fa]+1,in[u]=++timer;
    for(ri v:adj[u])
        if(v!=fa)dfs(v,u);
    out[u]=timer;
}
void solve(int u,int fa) {
    if(u!=1) {
        add(col[u]);
    }
    for(ri i=lt[u];i;i=nt[i]) {
        int x=ed[i];
        static int stk[Maxm+5][2];
        int top=0;
        for(ri j=1;j<=tot&&save[j].tim<x;j++) {
            int v=save[j].x;
            if(in[v]<=in[u]&&in[u]<=out[v]) {
                stk[++top][0]=v,stk[top][1]=col[v]; 
                erase(col[v]),add(col[v]=save[j].y);
            }
        }
        ans[x]=sum;
        while(top) {
            int u=stk[top][0],k=stk[top][1];--top;
            erase(col[u]),add(col[u]=k);
        }
    }
    for(ri v:adj[u])
        if(v!=fa)solve(v,u);
    if(u!=1) {
        erase(col[u]);
    }
}
void push() {
    if(cnt_e) {
        solve(1,0);
        for(ri i=1;i<=n;i++)lt[i]=0;
        cnt_e=0;
    }
    for(ri i=1;i<=tot;i++)col[save[i].x]=save[i].y;
    tot=0;
}
int main() {
    n=read(),m=read(),k=read();
    vector<int>x(n),y(n),c(n);
    for(ri i=1;i<n;i++) {
        x[i]=read(),y[i]=read(),c[i]=read();
        adj[x[i]].push_back(y[i]);
        adj[y[i]].push_back(x[i]);
    }
    dfs(1,0);
    for(ri i=1;i<n;i++) {
        int &p=x[i],&q=y[i];
        if(dep[p]<dep[q])swap(p,q);
        col[p]=c[i];
    }
    int Block=sqrt(n);
    for(ri i=1;i<=k;i++) {
        char c=read_char();
        if(c=='B') {
            int t=read(),y=read();
            save[++tot]=(Node){x[t],y,i};
            if(tot==Block)push();
        }
        else {
            int x=read();
            addedge(x,i);
        }
    }
    push();
    for(ri i=1;i<=k;i++)
        if(ans[i])print(ans[i],'\n');
    IO.write();
    return 0;
}