题目分析
题目描述
n个定理，每个定理需要a[i]的复习时间，除根节点外，每个定理必须先复习其前置定理，查询时对于q个复习策略，每个策略，每个策略需要复习k个指定定理，找到每个策略的最小时间。
思路分析
复习k个定理的最小时间——>在树中选择k个指定节点，求包含这些节点的所有祖先的权值和（最小连通子树的权重和）
要复习定理x，必须复习根到x路径上的所有定理，所以我们可以通过LCA算法来求解问题，找到通往每个节点路径上的全部权值和，再将通往按照时间戳排序后相邻两个节点的lca节点路径上的权值和删去，即可得到所求最小连通树的所有权值和啦~ （本题有多种解法，思路各有千秋，这里小编提供的是只用lca即可解决问题的解法）
话不多说上代码（牛客AC+详细注释）
#include<iostream>
#include<vector>
#include<string>
#include<cstring>
#include<algorithm>
//#include<bits/stdc++.h>
using namespace std;
#define int long long
const int MAX_N=500000+7,MAX_M=500000+7;int n,m,s;
int d[MAX_N];
int f[MAX_N][21];//倍增数组
int g=1,st[MAX_N];
int sum[MAX_N];//从根节点到当前节点路径的权值和
int a[MAX_N];//记录权值int head[MAX_N],cnt=-1;
struct Edge{int to,next;
}e[MAX_N*2];void dfs(int u,int fa){f[u][0]=fa;d[u]=d[fa]+1;st[u]=g++;sum[u]=sum[fa]+a[u];
// cout<<a[u]<<":"<<sum[u]<<endl;for(int i=1;(1<<i)<=d[u];i++){f[u][i]=f[f[u][i-1]][i-1];}for(int i=head[u];i!=-1;i=e[i].next){int v=e[i].to;if(v!=fa)dfs(v,u);}
}void add(int u,int v){e[++cnt].to=v;e[cnt].next=head[u];head[u]=cnt;
}int lca(int u,int v){if(d[u]<d[v]) swap(u,v);//用深度更大的向上跳跃，跳至于另一个在同一深度的位置，这里统一使用u去跳跃，所以将u变为深度更大的值for(int i=20;i>=0;i--){if(d[f[u][i]]>=d[v])u=f[u][i];}//跳至深度在同一位置if(u==v) return v;//特判，若u=v，则说明v节点在根节点到u节点的路径上，此时v就是v和u的公共祖先for(int i=20;i>=0;i--){if(f[u][i]!=f[v][i]){u=f[u][i];v=f[v][i];}//将深度相同的两个节点同时上跳 那么最后一次跳一定是其最小公共节点}return f[u][0];
}
signed main(){memset(head,-1,sizeof head);cin>>n;int u,v;for(int i=1;i<=n;i++){cin>>a[i];//输入权值}for(int i=1;i<n;i++){cin>>u>>v;add(u,v);add(v,u);//存图，无向图，所以存两遍}dfs(1,0);//进入dfs开始预处理数组（倍增数组 和 路径权值和数组），从1开始，1为根节点，父节点为0cin>>m;while(m--){cin>>s;vector<int> t;//定义一个数组，用于记录当前策略所需复习的知识点即所包含的节点int numb;for(int i=0;i<s;i++){cin>>numb;t.push_back(numb);}sort(t.begin(),t.end(),[&](int x,int y){return st[x]<st[y];});//按照时间戳排序，排序后的数组相邻两个节点在树上也是距离最近的//此时他们的LCA能够以最少得中间节点连接不同的子树分支int ans=0;for(int i=0;i<s;i++){ans+=sum[t[i]];//遍历节点，将根节点到每个节点的权值和全部相加，此时的结果并不是所求结果，因为此时的路径有重复，即两节点之间的公共祖先权值会重复相加}for(int i=0;i<s-1;i++){ans-=sum[lca(t[i],t[i+1])];//所以再次遍历，找到相邻两节点的公共祖先，减去其路径上的权值和}//此时的结果是去掉重复路径的结果 为争取值cout<<ans<<endl;}return 0;
}