P8844 [传智杯 #4 初赛] 小卡与落叶

简要题意

给出一个 \(n\) 个节点的以 \(1\) 为根的树，每一个节点 \(i\) 带权 \(w_i\)，初始时所有节点的权均为 \(0\)。有 \(m\) 个操作，支持以下操作：

1 x，对于所有树上节点 \(i\)，进行以下操作：

\[w_i=\begin{cases}1&(\operatorname{Depth}({i})\geq x)\\0&(\text{otherwise})\end{cases}
\]

2 x，询问以 \(x\) 为根的子树的所有节点的权值和。

\(1 \leq n,m \leq 10^{5}\)，允许离线。

思路

首先可以得出 2 操作的答案仅与之前的最后一次 1 操作有关，所以我们把操作离线下来，设最后一次 \(1\) 操作是 1 t，那么操作 2 v 其实是在求以 \(t\) 为根的子树中有多少个深度大于等于 \(t\) 的节点。统计深度自然想到按照深度建一个权值线段树森林。树上 DFS 处理询问。先把儿子合并到父亲上，然后直接回答查询即可（这里询问是线段树基本操作，不讲）。

时间复杂度 \(O(m\log n)\)。

代码

#include <bits/stdc++.h>

#define int long long

#define ls(i) (t[i].ls)

#define rs(i) (t[i].rs)

#define mid ((l+r)>>1)

using namespace std;

const int N = 1e5+5;

struct node{

	int ls,rs,v;

} t[N<<8];

int root[100005],tot;

int n,m;

inline void newnode(int &i){

	if(!i)i=(++tot);

}

void pushup(int i){

	t[i].v=t[ls(i)].v+t[rs(i)].v;

}

void insert(int p,int v,int &i,int l,int r){

	newnode(i);

	if(l==r){

		t[i].v++;

		return;

	}

	if(p<=mid){

		insert(p,v,ls(i),l,mid);

	}

	else{

		insert(p,v,rs(i),mid+1,r);

	}

	pushup(i);

}

void merge(int &x,int &y){

	if(x==0||y==0){

		if(y)x=y;

		if(x)y=x;

		return;

	}

	t[x].v+=t[y].v;

	merge(ls(x),ls(y));

	merge(rs(x),rs(y));

}

int query(int ql,int qr,int i,int l,int r){

	if(!i)return 0;

	if(ql<=l&&r<=qr){

		return t[i].v;

	}

	int res=0;

	if(ql<=mid){

		res+=query(ql,qr,ls(i),l,mid);

	}

	if(qr>mid){

		res+=query(ql,qr,rs(i),mid+1,r);

	}

	return res;

}

struct edge{

	int nxt,to;

} g[1000005];

int head[1000005],ec;

void add(int u,int v){

	g[++ec].nxt=head[u];

	g[ec].to=v;

	head[u]=ec;

}

int dep[1000005];

struct Query{

	int x,tmd;

	Query(int X=0,int TMD=0){

		x=X,tmd=TMD;

	}

};

int ret[1000005];

vector<Query> q[100005];

void dfs(int u,int fa){

	dep[u]=dep[fa]+1;

	for(int i=head[u];i;i=g[i].nxt){

		int v=g[i].to;

		if(v==fa)continue;

		dfs(v,u);

	}

}

void solve(int u,int fa){

	for(int i=head[u];i;i=g[i].nxt){

		int v=g[i].to;

		if(v==fa)continue;

		solve(v,u);

		merge(root[u],root[v]);

	}

	for(Query i:q[u]){

		ret[i.tmd]=query(i.x,n,root[u],1,n);

	}

}

signed main(){

	ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);

	cin>>n>>m;

	for(int i=1,u,v;i<n;i++){

		cin>>u>>v;

		add(u,v);add(v,u);

	}

	dfs(1,0);

	for(int i=1;i<=n;i++){

		insert(dep[i],1,root[i],1,n);

	}

	int last_dep=n+1,two_cnt=0;

	while(m--){

		int op,u;

		cin>>op>>u;

		if(op==1){

			last_dep=u;

			continue;

		}

		q[u].push_back(Query(last_dep,(++two_cnt)));

	}

	solve(1,0);

	for(int i=1;i<=two_cnt;i++){

		cout<<ret[i]<<'\n';

	}

	return 0;

}

巴特西

P8844 [传智杯 #4 初赛] 小卡与落叶

简要题意

思路

代码

最新文章

热门文章