前置知识
解法
维护点对信息，考虑点分治。
本题比 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;
}