BZOJ 3731 3731: Gty的超级妹子树 [树上size分块 !]

时间:2023-12-18 09:20:02

传送门

题意:一棵树,询问子树中权值大于k的节点个数,修改点权值,插入新点,断开边;强制在线


该死该死该死!!!!!!

MD我想早睡觉你知不知道

该死该死沙比提

断开边只会影响一个块,重构这个块就行了

如果断开的点$u$是这个块$p$的根,只修改原图和块图就好了

否则,把$u$子树在块中的部分从$p$里删除,放到一个新块里。并且,这些点连到的其他块的点,也要在块图上与$p$断开与新块相连

所以我们维护一个删除边的$mark$标记

WA:一开始原图加的是双向边,通过判断$fa$防止出错..后来$fa$会变化,然后判断$fa$就失灵了应该会一直$dfs$停不下来

所以一开始$dfs$就给双向边不用的那一条打上$mark$标记就好了

ps:

1.读入挂我直接复制了PoPoQQQ大爷的因为我有一次以为是读入导致WA

2.vector好快用这道题代码交上一题比我上一题跑的都快

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <vector>
using namespace std;
typedef long long ll;
const int N=2e5+;
inline int read1(){
char c=getchar();int x=,f=;
while(c<''||c>''){if(c=='-')f=-;c=getchar();}
while(c>=''&&c<=''){x=x*+c-'';c=getchar();}
return x*f;
}
namespace IOStream{
const int L=<<;
char buffer[L];
char *S,*T;
char Get_Char()
{
if(S==T)
{
T=(S=buffer)+fread(buffer,,L,stdin);
if(S==T)
return EOF;
}
return *S++;
}
int Get_Int()
{
int re=;
char c;
do c=Get_Char(); while(c<''||c>'');
while(c>=''&&c<='')
re=(re<<)+(re<<)+(c-''),c=Get_Char();
return re;
}
}
#define read IOStream::Get_Int int n,Q,a[N],op,u,x; struct meow{
vector<int> a;
inline void set() {sort(a.begin(), a.end());}
inline int count(int v) {return a.size() - (upper_bound(a.begin(), a.end(), v) - a.begin());}
inline void push(int v) {a.push_back(v);}
inline void insert(int v) {a.insert(lower_bound(a.begin(), a.end(), v), v);}
inline void erase(int v) {a.erase(lower_bound(a.begin(), a.end(), v));}
inline void replace(int x,int v) {if(x==v) return; erase(x); insert(v);}
inline int size() {return a.size();}
}b[N];
int m, pos[N], block; struct Graph4Block{
struct edge{int v,ne;} e[N<<];
int cnt, h[N], ine[N], mark[N<<];
inline void ins(int u,int v) {
e[++cnt]=(edge){v,h[u]}; h[u]=cnt;
ine[v]=cnt;
}
inline void dele(int u) {mark[ine[u]]=;}
int dfs(int u,int k) {
int ans= b[u].count(k);
for(int i=h[u];i;i=e[i].ne) if(!mark[i]) ans+=dfs(e[i].v, k);
return ans;
}
}G; struct edge{int v,ne;} e[N<<];
int cnt, h[N];
inline void ins(int u,int v) {
e[++cnt]=(edge){v,h[u]}; h[u]=cnt;
e[++cnt]=(edge){u,h[v]}; h[v]=cnt;
}
int fa[N], mark[N<<], ine[N];
inline void ins1(int u,int v) {
e[++cnt]=(edge){v,h[u]}; h[u]=cnt;
ine[v]=cnt; fa[v]=u;
}
inline void dele(int u) {fa[u]=; mark[ine[u]]=;} void dfs(int u) {
int p=pos[u];
b[p].push(a[u]);
for(int i=h[u];i;i=e[i].ne) if(!mark[i]) {
if(e[i].v!=fa[u]) {
fa[e[i].v]=u; ine[e[i].v]=i;
if(b[p].size() < block) pos[e[i].v]=p;
else pos[e[i].v]=++m, G.ins(p, m);
dfs(e[i].v);
} else mark[i]=;
}
} struct Block{
int dfs(int u,int k) {
int ans= a[u]>k;
for(int i=h[u];i;i=e[i].ne) if(!mark[i])
if(e[i].v!=fa[u]) {
if(pos[e[i].v] == pos[u]) ans+= dfs(e[i].v, k);
else ans+= G.dfs(pos[e[i].v], k);
}
return ans;
}
int Que(int u, int k) {return dfs(u, k);} void Cha(int u, int d) {b[pos[u]].replace(a[u], d); a[u]=d;} void Ins(int u, int d) {
a[++n]=d; ins1(u, n);
int p=pos[u];
if(b[p].size() < block) pos[n]=p, b[p].insert(a[n]);
else pos[n]=++m, b[m].push(a[n]), G.ins(p, m);
} void dfsSpl(int u,int p) {
b[p].erase(a[u]); pos[u]=m; b[m].push(a[u]);
for(int i=h[u];i;i=e[i].ne) if(!mark[i])
if(e[i].v!=fa[u]) {
if(pos[e[i].v] == p) dfsSpl(e[i].v, p);
else G.dele(pos[e[i].v]), G.ins(m, pos[e[i].v]);
}
}
void Split(int u){
int p=pos[u];
if(pos[fa[u]] != p) G.dele(p);
else m++, dfsSpl(u, p), b[m].set();
dele(u);
}
}B;
int main() {
freopen("in", "r", stdin);
n=read();
for(int i=;i<n;i++) ins(read(), read() );
for(int i=;i<=n;i++) a[i]=read();
block= pow(n, 0.6);
pos[]=++m; dfs();
for(int i=;i<=m;i++) b[i].set(); Q=read(); int lastans=;
for(int i=;i<=Q;i++) {
op=read();
u=read()^lastans;
if(op==) B.Split(u);
else{
x=read()^lastans;
if(op==) lastans=B.Que(u, x), printf("%d\n",lastans);
else if(op==) B.Cha(u, x);
else B.Ins(u, x);
}
}
}