看原题请戳这里

思路

一道简单的 DP。

首先看数据范围是 $n\le 10 ^ 5$，我们便可以判断，这道题我们需要的时间复杂度是 $O(n)$ 或 $O(n\log n)$。
再次回到题面，设节点 $u$ 的左儿子和右儿子的宽度分别为 $lson_u$ 和 $rson_u$，我们发现，当 $v$ 在 $u$ 的左子树中时，硬币向 $v$ 节点移动这一步所需要花费的次数为 $\max(0,rson_u-lson_u)$。
同时我们知道 $v$ 总共需要经过的次数为 $1$，于是我们便可以从节点 $v$ 往上一步步反推出从根节点到 $v$ 所需的次数。

具体代码过程

1. dfs $O(n)$ 查询节点 $v$ 的位置。
2. 在 dfs 回溯的过程中加上硬币从当前节点移动到下一个节点所需的次数（如果该连边的宽度小于 $ans$，直接输出 $-1$）。

时间复杂度

节点数量为 $n$，最坏情况下每个节点经过一次，所以时间复杂度 $O(n)$。

AC 代码

码风不太好

#include<bits/stdc++.h>
using namespace std;
const int N=1e5;
long long n,v,lson[N+2][2],rson[N+2][2],flag,ans;
void dp(long long now){
	if(now==v){
		flag=1,ans=1;
		return ;
	}
	if(lson[now][0]){
		dp(lson[now][0]);
		if(flag){
			if(lson[now][1]<ans){
				cout<<"-1";
				exit(0);
			}
			lson[now][1]-=ans;
			if(lson[now][1]<rson[now][1])ans=ans+rson[now][1]-lson[now][1]-1;
            return ;
		}
	}
	if(rson[now][0]){
		dp(rson[now][0]);
		if(flag){
			if(rson[now][1]<ans){
				cout<<"-1";
				exit(0);
			}
			rson[now][1]-=ans;
			if(rson[now][1]<=lson[now][1])ans=ans+lson[now][1]-rson[now][1];
		}
	}
	return ;
}
int main(){
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++)cin>>lson[i][0]>>lson[i][1]>>rson[i][0]>>rson[i][1];
	cin>>v;
	dp(1);
	cout<<ans;
	return ( 0 - 0 );
}