自动搬运

查看原文

来自洛谷，原作者为

	Purslane AFO

搬运于2025-08-24 23:04:18，当前版本为作者最后更新于2024-11-21 19:50:16，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

Solution

有一只青蛙这道题写了一个月，后面忘了。

算出每个叶子需要的拐弯次数。

再加回去就行了。也可以拍成序列然后前缀和。

#include<bits/stdc++.h>
#define ffor(i,a,b) for(int i=(a);i<=(b);i++)
#define roff(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
const int MAXN=200000+10;
int n,k,q,cnt[MAXN],dp[MAXN],pre[MAXN],dfn[MAXN],tot,sze[MAXN],o[MAXN];
vector<int> G[MAXN];
void dfs(int u,int f) {
	dfn[u]=++tot,sze[u]=1;
	if(f<=1||o[u]==o[f]) dp[u]=dp[f];
	else dp[u]=dp[f]+1;
	for(auto v:G[u]) dfs(v,u),sze[u]+=sze[v];
	return ;
}
int main() {
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>n>>k>>q;
	ffor(i,1,n) {
		int cnt;
		cin>>cnt;
		if(cnt==2) {
			int l,r;
			cin>>l>>r,o[l]=0,o[r]=1;
			G[i].push_back(l),G[i].push_back(r); 
		}
	}
	dfs(1,0);
	ffor(i,1,n) if(dp[i]<=k&&G[i].size()==0) pre[dfn[i]]++;
	ffor(i,1,n) pre[i]+=pre[i-1];
	ffor(i,1,q)	{
		int u;
		cin>>u;
		cout<<pre[dfn[u]+sze[u]-1]-pre[dfn[u]-1]<<'\n';
	}
	return 0;
}