题解归档 - cf343D

本文由 cf-code 本地题解库自动归档；公开内容以本地 AC/验证版本为准。

• 本地编号：cf343D
• 本地来源：problems/cf343D/idea.md
• 题目链接：https://codeforces.com/contest/343/problem/D
• 原始标题：343D — Water Tree

思路

343D — Water Tree

题意

根为 1 的有根树，初始全空。三种操作：

1. 填满 $v$ 的子树（$v$ 及所有后代）
2. 清空 $v$ 及其所有祖先（到根路径）
3. 查询 $v$ 是否非空

$ n,q \le 5\times 10^5$。

做法

树链剖分（HLD）+ 线段树区间赋值

• DFS 序 dfn：子树对应连续区间 [dfn[v], dfn[v]+sz[v]-1]
• 操作 1：子树区间赋 1
• 操作 2：根到 $v$ 的重链路径区间赋 0（while top[x]!=top[1] 跳链）
• 操作 3：单点查询 dfn[v]

线段树维护懒标记 lazy=-1/0/1 表示区间赋值。

实现注意

• 禁止 vector<ll> g[maxn]（$5\times10^5$ 个 vector 启动即崩）；读入 $n$ 后 ss.assign(n+1, {})
• 首次提交 CE：全局 vector<ll>ss[maxn+5] 在 CF 编译器上无法通过；已改为 vector<vector<ll>>ss + t/lazy 动态数组
• 线段树 upd 对无交集区间必须 return，否则叶子会死递归
• 查分时 TESTING/COMPILING/RUNNING 是非终态，需要继续等待。

Catalog

lib_target: 图论(树链剖分).cpp — AC 后沉淀模板。

验证

• 样例通过
• stress.py -n 100+ 与 brute.cpp 对拍

代码

来源：problems/cf343D/solution.cpp

/* Author: likely
 * Time: 2026-06-08 02:41:27
**/
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn=500005;
ll n,q,i,j,k,u,v,op,cnt,ans,pd,cur,dq;
vector<vector<ll>>ss;
ll fa[maxn+5],dep[maxn+5],sz[maxn+5],son[maxn+5],top[maxn+5],dfn[maxn+5];
vector<ll>t,lazy;
void pushdown(ll o){
    if(lazy[o]!=-1){
        t[o*2]=lazy[o],lazy[o*2]=lazy[o];
        t[o*2+1]=lazy[o],lazy[o*2+1]=lazy[o];
        t[o]=lazy[o],lazy[o]=-1;
    }
}
void upd(ll o,ll l,ll r,ll ql,ll qr,ll val){
    if(ql>r or qr<l) return;
    if(ql<=l and r<=qr){
        t[o]=val,lazy[o]=val;
        return;
    }
    pushdown(o);
    ll mid=(l+r)/2;
    if(ql<=mid) upd(o*2,l,mid,ql,qr,val);
    if(qr>mid) upd(o*2+1,mid+1,r,ql,qr,val);
}
void upd(ll l,ll r,ll val){
    if(l>r) return;
    upd(1,1,n,l,r,val);
}
ll qry(ll o,ll l,ll r,ll p){
    if(l==r) return t[o];
    pushdown(o);
    ll mid=(l+r)/2;
    if(p<=mid) return qry(o*2,l,mid,p);
    return qry(o*2+1,mid+1,r,p);
}
void dfs1(ll x){
    ll zc,pd;
    sz[x]=1,son[x]=0;
    for(zc=0;zc<(ll)ss[x].size();zc++){
        pd=ss[x][zc];
        if(pd==fa[x]) continue;
        fa[pd]=x,dep[pd]=dep[x]+1;
        dfs1(pd);
        sz[x]+=sz[pd];
        if(sz[pd]>sz[son[x]]) son[x]=pd;
    }
}
void dfs2(ll x,ll tp){
    ll zc,pd;
    top[x]=tp,dfn[x]=++cnt;
    if(son[x]) dfs2(son[x],tp);
    for(zc=0;zc<(ll)ss[x].size();zc++){
        pd=ss[x][zc];
        if(pd==fa[x] or pd==son[x]) continue;
        dfs2(pd,pd);
    }
}
void upd_sub(ll x,ll val){
    upd(dfn[x],dfn[x]+sz[x]-1,val);
}
void upd_path(ll x,ll val){
    while(top[x]!=top[1]){
        upd(dfn[top[x]],dfn[x],val);
        x=fa[top[x]];
    }
    upd(dfn[1],dfn[x],val);
}
int main(){
    cin>>n;
    ss.assign(n+1,vector<ll>());
    for(i=1;i<n;i++){
        cin>>u>>v;
        ss[u].push_back(v),ss[v].push_back(u);
    }
    t.assign(4*n+5,0),lazy.assign(4*n+5,-1);
    fa[1]=0,dep[1]=0;
    dfs1(1),cnt=0,dfs2(1,1);
    cin>>q;
    while(q--){
        cin>>op>>v;
        if(op==1) upd_sub(v,1);
        else if(op==2) upd_path(v,0);
        else cout<<qry(1,1,n,dfn[v])<<"\n";
    }
    return 0;
}