景区导游详细注释--先暴力->再借助最小公共祖先（树链剖分）优化

解题思路:
游览顺序为2 6 5 1，当跳过中间某个景点时(例如6)要花费的时间为总时间减去该景点与前一个景点的时间（2->6)，再减去该景点与后一个景点的时间（6->5），最后再加上前一个景点的时间到后一个景点的时间（2->5）,跳过第一个或者最后一个时只需要减去后一段或前一段时间；
注意事项:

参考代码:

先看暴力算法

#include#define ll long long 
using namespace std;
typedef pair pii;
const int N = 1e5+10;
map id;//id[{x,y}]表示两个点x到y之间的距离 
vectoredge[N];//edge[x]表示x点的邻接点数组 
int n,m;
ll ans = 0;//dfs函数中统计 x到y 时间 
bool v[N];//是否访问过该点的标记 


bool dfs(int st,int ed){//st起点，ed终点 
	for(int i=0;in>>m;
	int s[m];
	for(int i=1;i>x>>y>>l;
		edge[x].push_back(y);//把y加入x的邻接点数组中 
		edge[y].push_back(x);//把x加入y的邻接点数组中 
		id[{x,y}] = id[{y,x}] = l;//记录x,y间的时间 
	}
	for(int i=0;i>s[i];
	}
	ll sum = 0;//记录整个路线的总和时间 
	for(int i=0,j=1;j<m;i++,j++){//求整个路线的总和时间 ，依次传入两个点 
		ans = 0;//清除之前的数据 可以加入到dfs函数中 
		memset(v,false,sizeof(v)); //重置访问数组 
		v[s[i]] = true;//起点访问标记 
		dfs(s[i],s[j]);	
		id[{s[i],s[j]}] = ans;//记录这两点的 时间 
		id[{s[j],s[i]}] = ans;
		sum+=ans;//加入sum	
	}
	ans = 0;	
	for(int x=0;x<m;x++){//x为游览路线中跳过点的下标 
		if(x==0){//第一个点：用总时间减去第一个点到他后面那个点的时间就是跳过顶点时 需要的时间
			//例如1 2 3 4；不访问1时用总时间减去1到2的时间即为所求 
			cout<<sum - id[{s[x],s[x+1]}]<<" ";
		}
		else if(x==m-1){//最后点与上面同理 
			cout<<sum - id[{s[x-1],s[x]}]<<" ";
		}
		else{//中间的点就用总的时间减去该点前一个点到他的时间，再减去他到他后一个点的时间，再加上
		//他前一个点到他后一个点的时间
		//例如：2 6 5 1；跳过6时，用总时间减去2到6时间，再减去6到5时间，再加上2到5时间即为所求 
			ll temp1 = id[{s[x-1],s[x]}];//该点前一个点到他的时间
			ll temp2 = id[{s[x],s[x+1]}];//他到他后一个点的时间
			ans = 0;
			memset(v,false,sizeof(v));
			v[s[x-1]] = true;
			dfs(s[x-1],s[x+1]);
			ll temp3 = ans;//他前一个点到他后一个点的时间
			ll temp4 = sum - temp1 - temp2 +  temp3;//所求时间 
			cout<<temp4<<" ";	
		}
		ans = 0;
	}
}
int main(){
	solve();
	return 0;
}

接下来是引入最小公共祖先(用的是数链剖分)优化后的代码，两者大体思路一致

#include#define ll long long 
using namespace std;
typedef pair pii;
const int N = 1e5+10;
map id;
vectoredge[N];
int n,m;

ll sum[N];//sum[i]表示i这个点到我们指定的根节点u的时间 要开long long 


//树链剖分：
int fa[N],son[N],sz[N];//fa[u]存u的父节点，son[u]u的重儿子，sz[u]u为根节点的子树节点数(包括自己) 
int top[N],dep[N];//top[u]指u所在的重链顶点(是一个轻儿子节点)   dep[u]u所在的层级 
//以上部分数组再后面都要初始化为0

void dfs1(int u,int father){//完善 fa[],sz[],dep[]
	fa[u] = father,dep[u] = dep[father] + 1,sz[u] = 1;//sz[u] = 1自己 
	for(int v : edge[u]){
		if(v==father) continue;
		dfs1(v,u);
		sz[u] += sz[v];//节点大小加上子节点的大小 
		if(sz[son[u]] < sz[v]) son[u] = v;
	}	
} 

//初始调用dfs2(1,1) 
void dfs2(int u,int t){//完善top[] 
	top[u] = t;
	if(!son[u]) return ;//没有重儿子就返回
	dfs2(son[u],t);//如果有重儿子就深入遍历 连接这一条重儿子链top都为t
	for(int v : edge[u]) {
		if(v==fa[u] || v==son[u]) continue;//重儿子和父节点不在遍历
		dfs2(v,v);//轻儿子节点的top为他自己 
	}
}

int lca(int u,int v){//找两个节点的最小公共祖先 
	while(top[u]!=top[v]){//u,v节点不在一条重链上 
		if(dep[top[u]] < dep[top[v]]) swap(u,v);//让u始终为重链顶点更深的那一方 
		u = fa[top[u]] ;//u向上跳 
	} 
	return dep[u] < dep[v] ? u : v;//返回u，v层次更低的那一方 
} 


//树链剖分--end


void cal_sum(int u){//初始化sum数组
	for(int v : edge[u]){
		if(v==fa[u]) continue;//防止1到2又从2到1
		//假设支链1->3->5,5到1的时间为3到5的时间加上3到1的时间
		sum[v] = id[{v,u}] + sum[u];
		cal_sum(v);
	}	
}

void solve(){
	//数据初始化 
	memset(sz,0,sizeof(sz)); 
	memset(dep,0,sizeof(dep)); 
	memset(son,0,sizeof(son));
	memset(sum,0,sizeof(sum));	
	cin>>n>>m;
	int s[m];
	for(int i=1;i>x>>y>>l;
	    edge[x].push_back(y);
	    edge[y].push_back(x);
	    id[{x,y}] = id[{y,x}] = l;
	}
	for(int i=0;i>s[i];
	}
	
	dfs1(1,0);
	dfs2(1,1);
	cal_sum(1);//指定1为根节点sum数组记录了每个点到1的时间 
//数据初始化 end 

	ll sum_ = 0;//原始浏览景点的总时间 
	for(int i=0;i<m-1;i++){
		//此时任意两个点u，v之间的时间为： u到1的时间加上v到1的时间
		//减去2倍的多余部分时间(多余部分是指最小公共祖先到1的时间)  注意乘上2 
		sum_ += sum[s[i]] + sum[s[i+1]] - 2*sum[lca(s[i],s[i+1])];
	}
	//以下部分思路与暴力一致 
	for(int i=0;i<m;i++){
		ll temp = sum_;
		if(i==0){
			temp -= sum[s[i]] + sum[s[i+1]] - 2*sum[lca(s[i],s[i+1])];
		}
		else if(i==m-1){
			temp -= sum[s[i-1]] + sum[s[i]] - 2*sum[lca(s[i-1],s[i])];
		}
		else{		
			temp -= sum[s[i-1]] + sum[s[i]] - 2*sum[lca(s[i-1],s[i])];
			temp -= sum[s[i]] + sum[s[i+1]] - 2*sum[lca(s[i],s[i+1])];
			temp += sum[s[i-1]] + sum[s[i+1]] - 2*sum[lca(s[i-1],s[i+1])];
		}
		cout<<temp<<" ";
	}
}
int main(){
	solve();
	return 0;
}