萌新求助边分治

大概就是三度化过后边分治，交上去似乎又 WA 又 T，不太会了/kk

思路是把两个子树的路径拿出来然后按照黑点个数排序，然后单调队列。

#include<bits/stdc++.h>
using namespace std;
template <typename T>
inline void read(T &x){
    x=0;bool f=false;char ch=getchar();
    while(!isdigit(ch)){f|=ch=='-';ch=getchar();}
    while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
    x=f?-x:x;
    return ;
} 
template <typename T>
inline void write(T x){
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10^48);
    return ;
}
#define ll long long
const int N=6e5+5,INF=1e9+7;
ll Ans;
int n,m,k,tot;
int head[N],to[N],nex[N],val[N],idx;
inline void add(int u,int v,int w=0){
    nex[++idx]=head[u];
    to[idx]=v;
    val[idx]=w;
    head[u]=idx;
    return ;
}
typedef pair<int,int> PII;
vector<PII> vec[N];
void Dfs(int x,int fa){
    for(int i=head[x];i;i=nex[i]){
        int y=to[i];
        if(y==fa) continue;
        vec[x].push_back(make_pair(y,val[i]));Dfs(y,x);
    }
    return ;
}
void ReBuild(){
    idx=1;memset(head,0,sizeof(head));
    for(int i=1;i<=tot;i++){
        const int len=vec[i].size();
        if(len<=2){
            for(auto v:vec[i]) add(i,v.first,v.first<=n?v.second:0),add(v.first,i,v.first<=n?v.second:0);
        }
        else{
            int s1=++tot,s2=++tot;
            add(s1,i,0),add(i,s1,0),add(s2,i,0),add(i,s2,0);
            for(int j=0;j<len;j++) if(j&1) vec[s1].push_back(vec[i][j]);else vec[s2].push_back(vec[i][j]);
        }
    }
    return ;
}
int siz[N],Size,Max,Rt1,Rt2,Edge,cnt1,cnt2,a[N];
bool vis[N];
typedef pair<int,int> PII;
PII ls[N],rs[N];
void GetEdge(int x,int fa){
    siz[x]=1;
    for(int i=head[x];i;i=nex[i]){
        int y=to[i];
        if(y==fa||vis[i]) continue;
        GetEdge(y,x);
        const int Now=max(siz[y],Size-siz[y]);
        if(Now<Max) Max=Now,Rt1=x,Rt2=y,Edge=i; 
    }
    return ;
}
void GetPath(int x,int fa,int dis,int num,int tag){
    if(x<=n){
        if(tag==0) ls[++cnt1]=make_pair(num,dis);
        else rs[++cnt2]=make_pair(num,dis);
    }
    for(int i=head[x];i;i=nex[i]){
        int y=to[i];
        if(y==fa||vis[i]) continue;
        GetPath(y,x,dis+val[i],num+a[y],tag);
    } 
    return ;
}
void Divide(int x){
    if(Size==1) return ;
    Max=INF;Rt1=Rt2=Edge=0;
    GetEdge(x,0);
    if(!Edge) return ;
    vis[Edge]=vis[Edge^1]=true;
    cnt1=cnt2=0;
    GetPath(Rt1,0,0,a[Rt1],0),GetPath(Rt2,0,0,a[Rt2],1);
    sort(ls+1,ls+cnt1+1),sort(rs+1,rs+cnt2+1);
    int posr=1,Maxdep=0;
    for(int i=cnt1;i>=1;i--){
        while(posr<=cnt2&&rs[posr].first+ls[i].first<=k) Maxdep=max(Maxdep,rs[posr].second),posr++;
        if(posr!=1) Ans=max(Ans,1ll*(ls[i].second+Maxdep+val[Edge]));
    }
    int Siz1=Size-siz[Rt2],Siz2=siz[Rt2],tmp1=Rt1,tmp2=Rt2;
    Size=Siz1,Divide(tmp1);
    Size=Siz2,Divide(tmp2);
    return ;
}
signed main(){
    read(n),read(k),read(m);
    for(int i=1;i<=m;i++){
        int x;read(x),a[x]=true;
    }
    for(int i=1;i<n;i++){
        int u,v,w;
        read(u),read(v),read(w);
        add(u,v,w),add(v,u,w);
    }
    Dfs(1,0);tot=n;ReBuild();Size=tot;Divide(1);
    write(Ans);
    return 0;
}