景区导游--LCA+树上前缀和

关键就是删点少删边，只删有关的边

LCA找最近祖先，树上前缀和记，画图找公式，特殊情况为删第一和最后

sum和前缀和开ll

#include<bits/stdc++.h>
using namespace std;
#define N 100011
typedef long long ll;
typedef pair<int,int> PII;
int n,k;
int l[N];
struct edge
{int v;ll t;
};
vector<struct edge> mp[N];
int fa[N][25];
int d[N];
ll sum[N];
void dfs(int u,int f)
{d[u]=d[f]+1;fa[u][0]=f;for(int i=1;i<=19;i++){fa[u][i]=fa[fa[u][i-1]][i-1];}for(int i=0;i<mp[u].size();i++){struct edge a=mp[u][i];if(a.v!=f){sum[a.v]=sum[u]+a.t;///建立树上前缀和 dfs(a.v,u);}}
}
int lca(int x,int y)///LCA找最近公共祖先 
{if(d[x]<d[y]) swap(x,y);for(int i=19;i>=0;i--){if(d[fa[x][i]]>=d[y]){x=fa[x][i];}}if(x==y) return x;for(int i=19;i>=0;i--){if(fa[x][i]!=fa[y][i]){x=fa[x][i];y=fa[y][i];}}return fa[x][0];
}
ll get_dist(int x,int y)//求x和y的距离 
{if(x==0||y==0)return 0;return sum[x]+sum[y]-2*sum[lca(x,y)];     
}
int main()
{ 
cin>>n>>k;
for(int i=0;i<n-1;i++)
{int u,v,t;cin>>u>>v>>t;mp[u].push_back({v,t});mp[v].push_back({u,t});
}
dfs(1,0);
for(int i=1;i<=k;i++)
{cin>>l[i];
}
ll an=0;
for(int i=1;i<=k-1;i++)
{an+=get_dist(l[i],l[i+1]);
}
for(int i=1;i<=k;i++)
{ll d1=get_dist(l[i],l[i-1]);///第一个的d1==0 ll d2=get_dist(l[i],l[i+1]);///最后一个的d2==0 ll d3=get_dist(l[i-1],l[i+1]);///画画图就知道公式 cout<<an-d2-d1+d3<<" ";///
}
return 0;
}