代码错哪了?
查看原帖
代码错哪了?
664744
_lqs_楼主2023/1/27 21:57
#include<bits/stdc++.h>
#define N 200005
using namespace std;
int n,m,i,j,ans,k,s;
int dis[N],h[N];
int p[N][25];
int a,b,aa[N];
double c;
struct AB{
	int a,b,n;
	double c;
}d[N << 1];
double lp[N];
void cun(int a,int b,double c){
	d[++k].a=a,d[k].b=b,d[k].c=c;
	d[k].n=h[a],h[a]=k;
}
void dfs(int s,int f){
	dis[s]=dis[f]+1;
	if(s==1) lp[s]=1.00;
	p[s][0]=f;
	for(int i=1;(1 << i) <= dis[s];i++){
		p[s][i]=p[p[s][i-1]][i-1];
	}
	for(int i=h[s];i;i=d[i].n){
		int b=d[i].b;
		double c=d[i].c;
		if(b!=f){
			lp[b]=lp[s]*c;
			dfs(b,s);
			int jian=(int)lp[s];
			lp[s]-=(double)jian;
		}
	}
}
int lca(int a,int b){
	if(dis[a]>dis[b]) swap(a,b);
	for(int i=20;i>=0;i--){
		if(dis[a] <= dis[b]-(1 << i)){
			b=p[b][i];
		}
	}
	if(a==b) return a;
	for(int i=20;i>=0;i--){
		if(p[a][i]==p[b][i]) continue;
		else{
			a=p[a][i];
			b=p[b][i];
		}
	}
	return p[a][0];
}
int main(){
//	printf("%.2lf",0.00/0.00);
	scanf("%d%d",&n,&m);
	for(i=1;i<=n;i++) scanf("%d",&aa[i]);
	for(i=1;i<n;i++){
		scanf("%d%d%lf",&a,&b,&c);
		cun(a,b,(double)c);
		cun(b,a,(double)c);
	}
	dfs(1,0);
//	for(i=1;i<=n;i++) printf("%.3lf\n",lp[i]);
	for(i=1;i<=m;i++){
		scanf("%d%d",&a,&b);
		int p=lca(a,b);
		if(lp[a]==0 || lp[p]==0 || lp[b]==0) printf("Yes\n");
		else{
			double sum=lp[a]/lp[p]*(lp[b]/lp[p])*aa[a];
			int sum1=(int)sum;
			if((double)sum1==sum) printf("Yes\n");
			else printf("No\n");
		}	
	}
	return 0;
}

求 hack

2023/1/27 21:57
加载中...