noip模拟16

代码实现
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+5;
const int maxm=2e6+5;
int read(){
	int x=0,f=1;
	char ch=getchar();
	while(!isdigit(ch)){
		if(ch==‘-‘)f=-1;
		ch=getchar();
	}
	while(isdigit(ch)){
		x=x*10+ch-48;
		ch=getchar();	
	}
	return x*f;
}
int n,c[maxn],dep[maxn],f[maxn][25],fa[maxn],hd[maxn],cnt,x;
struct Edge{
	int nxt,to;	
}edge[maxm];
void add(int u,int v){
	edge[++cnt].nxt=hd[u];
	edge[cnt].to=v;
	hd[u]=cnt;
	return ;
}
bool check(int k,int j,int i){
	return 1ll*(c[i]-c[j])*(dep[j]-dep[k])<=1ll*(c[j]-c[k])*(dep[i]-dep[j]); 
}
void dfs(int u){
	dep[u]=dep[fa[u]]+1;
	int p=fa[u];
	for(int i=20;i>=0;i--){
		if(f[p][i]<=1)continue;
		int t=f[p][i];
		if(check(f[t][0],t,u))p=t; 
	}
	if(p!=1){
		if(check(f[p][0],p,u))p=f[p][0];	
	}
	f[u][0]=p;
//	cout<<p<<endl;
	for(int i=1;i<=20;i++){
		f[u][i]=f[f[u][i-1]][i-1];	
	}
	for(int i=hd[u];i;i=edge[i].nxt){
		int v=edge[i].to;
		dfs(v);	
	}
	return ;
}
int main(){
	n=read();
	for(int i=1;i<=n;i++){
		c[i]=read();
	}
	for(int i=2;i<=n;i++){
		fa[i]=read();
		add(fa[i],i);	
	}
	dfs(1);
	for(int i=2;i<=n;i++){
//		cout<<i<<" "<<f[i][0]<<endl;
		printf("%.10lf\n",(double)(c[f[i][0]]-c[i])/(double)(dep[i]-dep[f[i][0]]));	
	}
	return 0;
}

noip模拟16

上一篇:二叉树的非递归遍历


下一篇:Object的扩展 Object.create、Object.defineProperty、Object.defineProperties