求树上最长路径使得经过的拥挤节点个数不超过K
//欢迎访问这个博客!http://www.cnblogs.com/luyouqi233/p/8036828.html
#include<cstdio> #include<algorithm> #include<cstring> #include<vector> #define N 200010 using namespace std; typedef long long ll; typedef pair<int,int>pii; int head[N],ecnt,dis[N],fa[N],son[N],sze[N],ans,n,m,k,que[N],t[N],nump[N],maxn[N]; //dis[i] i到根节点的距离,fa[i] 父亲,son[i] i的最大子树大小,sze[i] BFS时以i为根的子树大小(son[]和sze[])用来求重心 //t[i] 当前子树节点到子树根且经过至多i个黑点的路径的最大权值和 //nump[i] 统计i到根节点的路径上的黑点数 //maxn[i] 以根节点为起点,终点在前面已经搜过的子树中,且该路径至多经过i个黑点,这样的路径的最大权值和。 bool vis[N],iscrowd[N];//iscrowd[i] 是否是拥挤节点 inline int read() { int ret=0,neg=1; char j=getchar(); for (;j>'9' || j<'0';j=getchar()) if (j=='-') neg=-1; for (;j>='0' && j<='9';j=getchar()) ret=ret*10+j-'0'; return ret*neg; } struct edge { int nxt,v,w; }e[2*N]; vector <pair<int,int> > s; void add(int u,int v,int w) { e[++ecnt].v=v,e[ecnt].w=w,e[ecnt].nxt=head[u],head[u]=ecnt; e[++ecnt].v=u,e[ecnt].w=w,e[ecnt].nxt=head[v],head[v]=ecnt; } int calcG(int sv) { int u,v,mx=n,G,qn; que[qn=1]=sv,fa[sv]=0; for (int ql=1;ql<=qn;ql++) { sze[u=que[ql]]=1,son[u]=0; for (int i=head[u];i;i=e[i].nxt) { if (vis[v=e[i].v] || v==fa[u]) continue; fa[v]=u,que[++qn]=v; } } for (int ql=qn;ql>=1;ql--) { u=que[ql],v=fa[u]; if (qn-sze[u]>son[u]) son[u]=qn-sze[u]; if (son[u]<mx) G=u,mx=son[u]; if (!v) break; sze[v]+=sze[u]; if (sze[u]>son[v]) son[v]=sze[u]; } return G; } inline int getmaxp(int st,ll L) { int qn=0,maxp=0; que[++qn]=st; nump[st]=iscrowd[st]; dis[st]=L; fa[st]=0; maxp=max(maxp,nump[st]); for (int ql=1,u;ql<=qn;ql++) for (int i=head[u=que[ql]],v;i;i=e[i].nxt) { if (vis[v=e[i].v] || v==fa[u]) continue; fa[v]=u; dis[v]=dis[u]+e[i].w; nump[v]=nump[u]+iscrowd[v]; maxp=max(maxp,nump[v]); que[++qn]=v; } return maxp; } inline void getmaxt(int st) { int qn=0; que[++qn]=st; t[nump[st]]=max(t[nump[st]],dis[st]); for (int ql=1,u;ql<=qn;ql++) for (int i=head[u=que[ql]],v;i;i=e[i].nxt) { if (vis[v=e[i].v] || v==fa[u]) continue; t[nump[v]]=max(t[nump[v]],dis[v]); que[++qn]=v; } return ; } void solve(int x) { int G=calcG(x); vis[G]=1;s.clear(); for (int i=head[G],v;i;i=e[i].nxt) if (!vis[v=e[i].v]) s.push_back(pii(getmaxp(v,e[i].w),v)); sort(s.begin(),s.end()); if (iscrowd[G]) k--; for (int i=0;i<s.size();i++) { getmaxt(s[i].second); int now=0; if (i) { for (int j=s[i].first;j>=0;j--) { while (now+j<k && now<s[i-1].first) now++,maxn[now]=max(maxn[now],maxn[now-1]); if(now+j<=k)ans=max(ans,maxn[now]+t[j]); } } if (i!=s.size()-1) for (int j=0;j<=s[i].first;j++) maxn[j]=max(maxn[j],t[j]),t[j]=0; else for (int j=0;j<=s[i].first;j++) { if (j<=k) ans=max(ans,max(t[j],maxn[j])); maxn[j]=t[j]=0; } } if (iscrowd[G]) k++; for (int i=head[G],v;i;i=e[i].nxt) if (!vis[v=e[i].v]) solve(v); return ; } int main() { scanf("%d%d%d",&n,&k,&m); for (int i=1,x;i<=m;i++) iscrowd[read()]=1; for (int i=1,x,y,z;i<n;i++) x=read(),y=read(),z=read(),add(x,y,z); solve(1); printf("%d",ans); return 0; }