跳到主要内容

Heavy Buckets

· 阅读需 1 分钟

因为每个点仅一个出边，是不会出现多种选择的

所以可以倍增解决，同时记录点和距离即可

AC代码
Details
#include<bits/stdc++.h>
using namespace std;
#define QAQ return 
#define QWQ return 0;
#define ll long long
#define pii pair< int,int >

const int N=2e5+10;

int fa[N][31];
ll dis[N][31];

int main()
{
//	freopen( "txt.in","r",stdin );
//	freopen( "txt.out","w",stdout );
	ios::sync_with_stdio( false );
	cin.tie( nullptr ), cout.tie( nullptr );
	int n, q;
	cin>>n>>q;
	for( int i=1;i<=n;i++ ) cin>>fa[i][0], dis[i][0]=i;
	for( int bit=1;bit<=30;bit++ ) for( int i=1;i<=n;i++ ) fa[i][bit]=fa[fa[i][bit-1]][bit-1], dis[i][bit]=dis[i][bit-1]+dis[fa[i][bit-1]][bit-1];
	for( int i=1, t, b;i<=q;i++ )
	{
		cin>>t>>b;
		ll ans=0;
		for( int bit=30;bit>=0;bit-- ) if( ( t>>bit )&1 ) ans+=dis[b][bit], b=fa[b][bit];
		cout<<ans<<"\n";
	}
	QWQ	  
}

时间复杂度：O(nlogn)O(nlogn)