商务旅行求助

问题讨论区 提高段
1 
#include<iostream>
#include<math.h>
#include<algorithm>
#include<vector>
using namespace std;
int n,su=0,tt[30009],ne[30009],
be[30009],db[30009],dp[30009][17];
void add(int x,int y){
	su++;
	tt[su]=y;
	ne[su]=be[x];
	be[ ]=su;
}
void dfs(int x,int f){
//	cout<<endl;
//	cout<<x<<endl;
//	cout<<x<<' '<<f<<endl;
	db[x]=db[f]+1;
	dp[x][0]=f;
	for(int i=1;(1<<i)<=db[ ];i++){
		dp[x][i]=dp[dp[x][i-1]][i-1];
	}
//	cout<<x<<' '<<f<<endl;
//cout<<x<<endl;
	for(int i=be[x];i!=0;i=ne[i]){
//		cout<<i<<' '<<x<<endl;
//          cout<<x<<endl;
		if(tt[i]!=f&&tt[i]!=x){
//			cout<<x<<endl;
			dfs(tt[i],x);
		}
	}
}
int lca(int x,int y){
	if(db[x]<db[y]){
		swap(x,y);
	}
	for(int i=15;i>=0;i--){
		if(db[x]-(1<<i)>=db[y]){
			x=dp[x][i];
		}
	}
	if(x==y){
		return x;
	}
	for(int i=15;i>=0;i--){
		if(dp[x][i]!=dp[y][i]){
			x=dp[x][i];
			y=dp[y][i];
		}
	}
	return dp[x][0];
}
int main(){
cin>>n;
for(int i=0;i<n-1;i++){
	int x,y;
	cin>>x>>y;
	add(x,y);
	add(y,x);
//	cout<<'y'<<endl;
}
dfs(1,0);
int m;
cin>>m;
int d[m];
for(int i=0;i<m;i++){
	cin>>d[i];
}
long long sum=0;
sum+=db[d[0]]-1;
for(int i=0;i<m-1;i++){
	int o=lca(d[i],d[i+1]);
	sum+=db[d[i]]+db[d[i+1]]-2*db[o];
}
cout<<sum;
     return 0;
}
2

#include
#include<math.h>
#include
#include
using namespace std;
int n,su=0,tt[30009],ne[30009],
be[30009],db[30009],dp[30009][17];
void add(int x,int y){
su++;
tt[su]=y;
ne[su]=be;
be=su;
}
void dfs(int x,int f){
// cout<<endl;
// cout<<x<<endl;
// cout<<x<<’ ‘<<f<<endl;
db=db[f]+1;
dp[0]=f;
for(int i=1;(1<<i)<=db;i++){
dp[i]=dp[dp[i-1]][i-1];
}
// cout<<x<<’ ‘<<f<<endl;
//cout<<x<<endl;
for(int i=be;i!=0;i=ne[i]){
// cout<<i<<’ '<<x<<endl;
// cout<<x<<endl;
if(tt[i]!=f&&tt[i]!=x){
// cout<<x<<endl;
dfs(tt[i],x);
}
}
}
int lca(int x,int y){
if(db<db[y]){
swap(x,y);
}
for(int i=15;i>=0;i–){
if(db-(1<<i)>=db[y]){
x=dp[i];
}
}
if(x==y){
return x;
}
for(int i=15;i>=0;i–){
if(dp[i]!=dp[y][i]){
x=dp[i];
y=dp[y][i];
}
}
return dp[0];
}
int main(){
cin>>n;
for(int i=0;i<n-1;i++){
int x,y;
cin>>x>>y;
add(x,y);
add(y,x);
// cout<<‘y’<<endl;
}
dfs(1,0);
int m;
cin>>m;
int d[m];
for(int i=0;i<m;i++){
cin>>d[i];
}
long long sum=0;
sum+=db[d[0]]-1;
for(int i=0;i<m-1;i++){
int o=lca(d[i],d[i+1]);
sum+=db[d[i]]+db[d[i+1]]-2*db[o];
}
cout<<sum;
return 0;
}
代码没发好

3

dfs第二个for循环x会变成一个常数（28625）

1 个赞
4

@于嘉一 代码格式化一下

5

已AC,感谢大家（双向边要开双倍数组）