带 加点 删边的块状树。
加点在 bzoj3720 说过。
删边其实就是块顶打标记，记录其属于哪棵树，防止在dfs搜集答案时跑到别的树上。
然后暴力把所在块拆开。
好像用邻接表存图，直接在vector里删边也行？
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<vector>
using namespace std;
#define maxn 200001
int Res,Num;char C,CH[];
inline int Ge()
{
Res=;C='*';
while(C<''||C>'')C=getchar();
while(C>=''&&C<=''){Res=Res*+(C-'');C=getchar();}
return Res;
}
inline void P(int x)
{
Num=;if(!x){putchar('');puts("");return;}
while(x>)CH[++Num]=x%,x/=;
while(Num)putchar(CH[Num--]+);
putchar('\n');
}
typedef vector<int>::iterator ITER;
vector<int>List[maxn],Goto[maxn];
struct Graph
{
int v[maxn<<],first[maxn<<],next[maxn<<],en;
void AddEdge(const int &a,const int &b)
{v[++en]=b;next[en]=first[a];first[a]=en;}
};
Graph G,son;
int top[maxn],siz[maxn],sz,w[maxn],belong_tree[maxn];
bool vis[maxn],root[maxn];
int n,x,y,m,op,tree_num;
int ans,val,U;
void makeblock(int cur)
{
vis[cur]=true;
for(int i=G.first[cur];i;i=G.next[i])
if(!vis[G.v[i]])
{
son.AddEdge(cur,G.v[i]);
if(siz[top[cur]]<sz)
{
List[top[cur]].push_back(w[G.v[i]]);
siz[top[cur]]++;
top[G.v[i]]=top[cur];
}
makeblock(G.v[i]);
}
}
void makeGoto(int cur)
{
for(int i=son.first[cur];i;i=son.next[i])
{
if(top[son.v[i]]!=top[cur])
Goto[top[cur]].push_back(son.v[i]);
makeGoto(son.v[i]);
}
}
void dfs(int cur)//在Goto树上询问
{
ans+=( List[cur].end() - upper_bound( List[cur].begin() , List[cur].end() , val ) );
for(ITER it=Goto[cur].begin();it!=Goto[cur].end();it++)
if(belong_tree[*it]==belong_tree[cur])//通过标记控制在一棵树内
dfs(*it);
}
void dfs_block(int cur)//在块内询问
{
if(w[cur]>val) ans++;
for(int i=son.first[cur];i;i=son.next[i])
if(top[son.v[i]]==top[cur]) dfs_block(son.v[i]);
else if(belong_tree[son.v[i]]==belong_tree[top[cur]]) dfs(son.v[i]);
}
void query()
{
ans=;
if(U==top[U]) dfs(U);
else dfs_block(U);
P(ans);
}
void update()
{
List[top[U]].erase( lower_bound(List[top[U]].begin(),List[top[U]].end(),w[U]) );
w[U]=val;
List[top[U]].insert( lower_bound(List[top[U]].begin(),List[top[U]].end(),val+) , val );
}
void AddPoint()
{
n++;
if(siz[top[U]]<sz)
{
top[n]=top[U];
siz[top[n]]++;
}
else
{
top[n]=n;
siz[n]++;
Goto[top[U]].push_back(n);
belong_tree[n]=belong_tree[top[U]];
}
son.AddEdge(U,n);
w[n]=val;
List[top[n]].insert( lower_bound(List[top[n]].begin(),List[top[n]].end(),val+) , val );
}
void dfs_split(int cur)//设置每个块顶属于哪个树的标记
{
for(ITER it=Goto[cur].begin();it!=Goto[cur].end();it++)
if(belong_tree[cur]==belong_tree[*it])
dfs_split(*it);
belong_tree[cur]=tree_num;
}
void dfs_split_block(int cur)//把分裂的块的下半部分重构块
{
List[U].push_back(w[cur]);
for(int i=son.first[cur];i;i=son.next[i])
{
if(top[son.v[i]]==top[cur])
dfs_split_block(son.v[i]);
else if(belong_tree[son.v[i]]==belong_tree[top[U]])//顺手设置它下面的块的标记
{
Goto[U].push_back(son.v[i]);
dfs_split(son.v[i]);
}
siz[U]++;
}
top[cur]=U;
}
void dfs_remain_block(int cur)//把分裂的块的上半部分重构块
{
List[top[U]].push_back(w[cur]); siz[top[U]]++;
for(int i=son.first[cur];i;i=son.next[i])
if( (!root[son.v[i]]) && (top[son.v[i]]==top[cur]) )
dfs_remain_block(son.v[i]);
}
void Delete_Edge()
{
root[U]=true;
tree_num++;
if(U!=top[U])
{
List[top[U]].clear();siz[top[U]]=;
dfs_remain_block(top[U]);
sort(List[top[U]].begin(),List[top[U]].end());//重构分裂的块的上半部分
dfs_split_block(U);
belong_tree[U]=tree_num;
sort(List[U].begin(),List[U].end());//重构分裂的块的下半部分
}
else
dfs_split(U);
}
int main()
{
n=Ge();
for(int i=;i<n;i++)
{
x=Ge();y=Ge();
G.AddEdge(x,y);
G.AddEdge(y,x);
}
sz=sqrt((double)n*log2(n));
for(int i=;i<=n;i++)
{
w[i]=Ge();
top[i]=i;
siz[i]=;
}
makeblock();
for(int i=;i<=n;i++)
if(top[i]==i)
{
List[i].push_back(w[i]);
sort(List[i].begin(),List[i].end());
}
makeGoto();
root[]=true;
m=Ge();
for(int i=;i<=m;i++)
{
op=Ge();U=Ge();U^=ans;
if(!op){val=Ge();val^=ans;query();}
else if(op==){val=Ge();val^=ans;update();}
else if(op==){val=Ge();val^=ans;AddPoint();}
else Delete_Edge();
}
return ;
}