【做题记录】CodeForces343D Water Tree

题面翻译

• 给出一棵以 \(1\) 为根节点的 \(n\) 个节点的有根树。每个点有一个权值，初始为 \(0\)。
• \(m\) 次操作。操作有 \(3\) 种：
  1. 将点 \(u\) 和其子树上的所有节点的权值改为 \(1\)。
  2. 将点 \(u\) 到 \(1\) 的路径上的所有节点的权值改为 \(0\)。
  3. 询问点 \(u\) 的权值。
• \(1\le n,m\le 5\times 10^5\)。

所以说这可以用树链剖分来解决。
至于 2 、 3 操作，可以用线段树来维护（满足加法交换律的似乎都可以考虑线段树），但我不想写线段树，于是写了珂朵莉树 ODT （明显码量小了很多，但时间慢了很多）。

代码：

#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<cctype>
#include<set>
#include<algorithm>
typedef long long LL;
typedef unsigned long long ULL;
namespace FastIo{
    static char buf[100000],*p1=buf,*p2=buf,fw[100000],*pw=fw;
    #define gc p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++
    inline void pc(const char &ch){
    	if(pw-fw==100000)fwrite(fw,1,100000,stdout),pw=fw;
    	*pw++=ch;
	}
    #define fsh fwrite(fw,1,pw-fw,stdout),pw=fw
    struct QIO{
    	char ch;
    	int st[40];
    	template<class T>inline void read(T &x){
    		x=0,ch=gc;
    		while(!isdigit(ch))ch=gc;
    		while(isdigit(ch)){x=(x<<3)+(x<<1)+(ch^48);ch=gc;}
		}
		template<class T>inline void write(T a){
			do{st[++st[0]]=a%10;a/=10;}while(a);
			while(st[0])pc(st[st[0]--]^48);
			pc('\n');
		}
	}qrw;
}
using namespace FastIo;
#define NUMBER1 500000
#define P(A) A=-~A
#define fione_i(begin,end) for(register int i=begin;i<=end;P(i))
#define tt(u) for(register int i=head[u];i;i=e[i].next)
#define ODT set<KDL>::iterator
using std::swap;
using std::set;
using std::iterator;
struct EDGE{int next,to;}e[(NUMBER1<<2)+5];
struct KDL{
	int l,r;
	mutable int v;
	KDL(int l,int r=0,int v=0):l(l),r(r),v(v){}
	bool operator<(const KDL &A)const{return l<A.l;}
};
set<KDL>odt;
int n,cnt(0),tot(0),top[NUMBER1+5],fa[NUMBER1+5],size[NUMBER1+5],son[NUMBER1+5],id[NUMBER1+5],depth[NUMBER1+5],head[NUMBER1+5];
inline void add(const int &u,const int &v){e[++tot].next=head[u];head[u]=tot,e[tot].to=v;}
void dfs1(int u,int fath,int deep){
	depth[u]=deep,fa[u]=fath,size[u]=1;
	int ms(-1);
	tt(u){
		if(e[i].to==fath)continue;
		dfs1(e[i].to,u,deep+1);
		size[u]+=size[e[i].to];
		if(size[e[i].to]>ms)ms=size[e[i].to],son[u]=e[i].to;
	}
}
void dfs2(int u,int tf){
	id[u]=++cnt,top[u]=tf;
	if(!son[u])return;
	dfs2(son[u],tf);
	tt(u){
		if(e[i].to==fa[u]||e[i].to==son[u])continue;
		dfs2(e[i].to,e[i].to);
	}
}
ODT split(int p){
	ODT it=odt.lower_bound(KDL(p));
	if(it!=odt.end()&&it->l==p)return it;
	--it;
	int l=it->l,r=it->r,v=it->v;
	odt.erase(it);
	odt.insert(KDL(l,p-1,v));
	return odt.insert(KDL(p,r,v)).first;
}
inline void assign(int l,int r,int v){
	ODT itr=split(r+1),itl=split(l);
	odt.erase(itl,itr);
	odt.insert(KDL(l,r,v));
}
inline int intervalsum(int p){
	ODT it=split(p);
	return it->v;
}
inline void treechange(int p){
	int tp=top[p];
	while(tp!=1){
		assign(id[tp],id[p],0);
		p=fa[tp],tp=top[p];
	}
	assign(id[1],id[p],0);
}
signed main(){
	int m,x,y;
	qrw.read(n);
	fione_i(2,n){
		qrw.read(x);
		qrw.read(y);
		add(x,y);add(y,x);
	}
	odt.insert(KDL(1,n,0));
	dfs1(1,0,1);
	dfs2(1,1);
	qrw.read(m);
	while(m--){
		qrw.read(y);
		qrw.read(x);
		if(y==1)assign(id[x],id[x]+size[x]-1,1);
		else if(y==2)treechange(x);
		else qrw.write(intervalsum(id[x]));	
	}
	fsh;
    exit(0);
    return 0;
}