题目链接：
题意：给出一棵树，树上的节点为白色或黑色，树上的边有权值。求一条路径，包含的黑色节点不超过K的情况下使得长度最长？
思路：一条路径要么从根节点过要么不经过根节点，基于这样的思路我们可以使用分治。令G(i,j)表示根的i孩子所在子树中，从i向下最多经过j个黑色节点可以得到的最长路。那么对于根的任意两个孩子i1和i2，答案为:
其中若根节点为黑色节点则black[root]=1，否则为0。按照这个思路，对root的任意两个孩子都要这样计算一次，复杂度太高了。我们令dep[i]表示i向下最多可以经过多少黑色节点。首先，我们将所有孩子DFS一次，得到每个孩子的dep值，然后将dep升序。我们令p[i][j]表示前i个孩子中深度为j的最优值即最长路（这里p的第一维其实是可以省略的），那么对于root，假设有sum个孩子，计算root这一次复杂度就是sum*K。
int n,m,K,ans;vector<pair<int,int> > g[N];int visit[N];int s[N],Max[N];vector<int> V1,V2;int black[N],G[N],p[N];int tot;void DFS(int u,int pre){ s[u]=1; Max[u]=0; tot++; int i,v; FOR0(i,SZ(g[u])) { v=g[u][i].first; if(v==pre||visit[v]) continue; DFS(v,u); s[u]+=s[v]; if(s[v]>Max[u]) Max[u]=s[v]; } V1.pb(Max[u]); V2.pb(u);}int getRoot(int u){ V1.clear(); V2.clear(); tot=0; DFS(u,-1); int Min=INF,ans,i,temp; FOR0(i,SZ(V1)) { temp=max(V1[i],tot-V1[i]); if(temp<Min) Min=temp,ans=V2[i]; } return ans;}int dep[N],way[N];int getDep(int u,int pre){ int ans=0,i,v,temp; FOR0(i,SZ(g[u])) { v=g[u][i].first; if(!visit[v]&&v!=pre) { temp=getDep(v,u); if(temp>ans) ans=temp; } } return ans+black[u];}int U;int cmp(int x,int y){ return dep[g[U][x].first]<dep[g[U][y].first];}void getWay(int u,int sum,int dis,int pre){ G[sum]=max(G[sum],dis); int i,v,w; FOR0(i,SZ(g[u])) { v=g[u][i].first; w=g[u][i].second; if(visit[v]||v==pre) continue; getWay(v,sum+black[v],dis+w,u); }}void solve(int u,int pre){ u=getRoot(u); int i,j,v,w,sum=0; FOR0(i,SZ(g[u])) { v=g[u][i].first; if(!visit[v]) dep[v]=getDep(v,u),way[sum++]=i; } if(sum==0) return; U=u; sort(way,way+sum,cmp); v=g[u][way[sum-1]].first; for(i=0;i<=dep[v];i++) p[i]=-INF; int temp; FOR0(i,sum) { v=g[u][way[i]].first; w=g[u][way[i]].second; for(j=0;j<=dep[v];j++) G[j]=-INF; getWay(v,black[v],w,u); if(i!=0) { for(j=0;j<=K-black[u]&&j<=dep[v];j++) { temp=min(K-black[u]-j,dep[g[u][way[i-1]].first]); if(p[temp]!=-INF&&G[j]!=-INF) ans=max(ans,p[temp]+G[j]); } } for(j=0;j<=dep[v];j++) { p[j]=max(p[j],G[j]); if(j) p[j]=max(p[j],p[j-1]); if(j+black[u]<=K) ans=max(ans,p[j]); } } visit[u]=1; FOR0(i,SZ(g[u])) { v=g[u][i].first; if(!visit[v]) solve(v,u); }}int main(){ RD(n,K,m); int i; int x,y,z; FOR1(i,m) RD(x),black[x]=1; FOR1(i,n-1) { RD(x,y,z); g[x].pb(MP(y,z)); g[y].pb(MP(x,z)); } ans=0; solve(1,-1); PR(ans);}
