题意：
有n个座位和n − 1个通道，有n个人，每个人到达座位后需要花费a i 的时间才能坐下，坐人后的座位不能再被经过。1为入口，第i秒的时候第i个人进入，经过一个通道花费1 s,安排一种座位方案，使得所有人坐下花费的时间最短。
思路：
贪心的考虑，假设第x个人坐在座位y，d e p y 表示从1到y花费的时间，那么第x个人花费的时间为x + a x + d e p y 贪心的考虑，肯定是想让x + a x大的人对应d e p y小的座位，排个序取m a x就是答案。
代码：
#include<bits/stdc++.h> using namespace std; typedef long long ll;typedef unsigned long long ull; typedef pair<ll,ll>PLL;typedef pair<int,int>PII;typedef pair<double,double>PDD; #define I_int ll inline ll read(){ll x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;} #define read read() #define rep(i, a, b) for(int i=(a);i<=(b);++i) #define dep(i, a, b) for(int i=(a);i>=(b);--i) ll ksm(ll a,ll b,ll p){ll res=1;while(b){if(b&1)res=res*a%p;a=a*a%p;b>>=1;}return res;} const int maxn = 1e5 + 10; int n,f[maxn],dep[maxn]; vector<int>g[maxn]; struct node{ int id,val; }a[maxn]; bool cmp(node a,node b){ return a.id+a.val<b.id+b.val; } void bfs(){ memset(dep,0x3f,sizeof dep); queue<int>q;q.push(1);dep[1]=0; while(!q.empty()){ int t=q.front();q.pop(); for(auto tt:g[t]){ if(dep[tt]>dep[t]+1){ dep[tt]=dep[t]+1; q.push(tt); } } } } int main() { int _=read; while(_--){ n=read; rep(i,1,n) g[i].clear(); rep(i,1,n-1){ f[i]=read; g[f[i]].push_back(i+1); g[i+1].push_back(f[i]); } rep(i,1,n) a[i].val=read,a[i].id=i; bfs(); sort(a+1,a+1+n,cmp); sort(dep+1,dep+1+n);reverse(dep+1,dep+1+n); int ans=0; rep(i,1,n){ ans=max(ans,dep[i]+a[i].id+a[i].val); } cout<<ans<<endl; } return 0; } /* */
