题解：P11108 [ROI 2023 Day 2] 蜗牛与富士山

Purslane · 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;
}