题目传送门
前置知识
点分治 | 树状数组
解法
维护点对信息，考虑点分治。
本题比 luogu P4149 [IOI2011] Race 多了个前缀查询 \(\max\)。套个支持单点修改、区间查询 \(\max\) 的数据结构即可。
直接线段树维护区间 \(\max\) 貌似会 TLE，换成树状数组维护前缀 \(\max\) 即可。
- 注意数组偏移问题。
代码
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define sort stable_sort
#define endl '\n'
struct node
{int nxt,to,w;
}e[400010];
int head[400010],col[400010],ask,ans=0,cnt=0;
void add(int u,int v,int w)
{cnt++;e[cnt].nxt=head[u];e[cnt].to=v;e[cnt].w=w;head[u]=cnt;
}
struct BIT
{ int c[400010];int lowbit(int x){return (x&(-x));}void init(){memset(c,-0x3f,sizeof(c));}void add(int n,int x,int val){for(int i=x;i<=n;i+=lowbit(i)){c[i]=max(c[i],val);}}int getsum(int x){int ans=-0x3f3f3f3f;for(int i=x;i>=1;i-=lowbit(i)){ans=max(ans,c[i]);}return ans;}void clear(int n,int x){for(int i=x;i<=n;i+=lowbit(i)){c[i]=-0x3f3f3f3f;}}
}T;
struct Divide_On_Tree
{int siz[400010],weight[400010],vis[400010],dis[400010],sum[400010],tmp[400010],d[400010],center=0;queue<int>q;void init(int n){T.init();center=0;get_center(1,0,n);get_siz(center,0);divide(center);}void get_center(int x,int fa,int n){siz[x]=1;weight[x]=0;for(int i=head[x];i!=0;i=e[i].nxt){if(e[i].to!=fa&&vis[e[i].to]==0){get_center(e[i].to,x,n);siz[x]+=siz[e[i].to];weight[x]=max(weight[x],siz[e[i].to]);}}weight[x]=max(weight[x],n-siz[x]);if(weight[x]<=n/2){center=x;}}void get_siz(int x,int fa){siz[x]=1;for(int i=head[x];i!=0;i=e[i].nxt){if(e[i].to!=fa&&vis[e[i].to]==0){get_siz(e[i].to,x);siz[x]+=siz[e[i].to];}}}void get_dis(int x,int fa,int rt){if(sum[x]+col[rt]<=ask){tmp[0]++;tmp[tmp[0]]=sum[x];d[tmp[0]]=dis[x];for(int i=head[x];i!=0;i=e[i].nxt){if(e[i].to!=fa&&vis[e[i].to]==0){dis[e[i].to]=dis[x]+e[i].w;sum[e[i].to]=sum[x]+col[e[i].to];get_dis(e[i].to,x,rt);}}}}void divide(int x){T.add(ask+2,0+1,0);q.push(0);vis[x]=1;for(int i=head[x];i!=0;i=e[i].nxt){if(vis[e[i].to]==0){tmp[0]=0;dis[e[i].to]=e[i].w;sum[e[i].to]=col[e[i].to];get_dis(e[i].to,x,x);for(int j=1;j<=tmp[0];j++){ans=max(ans,T.getsum(ask-tmp[j]+1)+d[j]);} for(int j=1;j<=tmp[0];j++){T.add(ask+2,tmp[j]+col[x]+1,d[j]);q.push(tmp[j]);}}}while(q.empty()==0){T.clear(ask+2,q.front()+col[x]+1);q.pop();}for(int i=head[x];i!=0;i=e[i].nxt){if(vis[e[i].to]==0){center=0;get_center(e[i].to,x,siz[e[i].to]);get_siz(center,0);divide(center);}}}
}D;
int main()
{int n,m,u,v,w,i;cin>>n>>ask>>m;for(i=1;i<=m;i++){cin>>u;col[u]=1;}for(i=1;i<=n-1;i++){cin>>u>>v>>w;add(u,v,w);add(v,u,w);}D.init(n);cout<<ans<<endl;return 0;
}
