**【描述】**
L在N个不同的城市做生意，他收到了N个不同城市的N份交易订单。在这N个城市之间有一些低速公路，这些低速公路都有自己的一个载重上限，这限制了你在这条公路上前进的时候能够携带的货物数量。除了低速公路之外，还有些城市修了慢速铁路站。对于修了慢速铁路站的城市，你可以乘坐慢速火车在这些城市之间往返而不受载重上限的限制。

L现在要按照顺序来处理这N份订单，他可以自由选择自己的路线。这N份订单每份订单可能是要从客户中买进一些货物，或者售出一些货物，并且有可以交易的上限存在。L希望自己在交易完最后一笔订单之后自己不会剩下货物，并且在整个过程中不会出现因载重限制丢弃货物的情况（意味着你并不会每次都以最大量买入）。在满足以上所有条件的情况下，L希望自己的交易量最大（即买入卖出都尽量多），那么最大的交易量应该是怎样的呢？

**【数据范围与规定】**

对于20%的数据，N≤100，M≤200。

对于50%的数据，N≤3000，M≤6000。

对于100%的数据，N≤10^5，N-1≤M≤2*10^5，0≤Q≤N，0<|x|<10^9，保证任意两个城市之间可以通过低速公路连通。

做法:

注意建图的细节。

先跑最大瓶颈路（最大生成树+lca维护两点间最小距离）， 最后处理成一条链贪心转移即可（只需要输出卖出的方案）

 

代码：

#include<bits/stdc++.h>
using namespace std;
#define re register
#define int long long
const int INF=1e14+9;
const int maxm=6e5+10,maxn=2e5+10;
int n,m,Q,on;
struct edge{
int v,nxt,w;
}e[maxm];
int head[maxn],cnt=0;
inline void _add(int u,int v,int w){
e[++cnt]=(edge){v,head[u],w};
head[u]=cnt;
}
struct pi{
int u,v,w;
}p[maxm];
bool cmp(pi a,pi b){
return a.w>b.w;
}
int a1,a2,a3;
int ord[maxn];
bool col[maxn];
int ff[maxn];
int find(int u){
return ff[u]==0? u:ff[u]=find(ff[u]);
}
inline void build(){
sort(p+1,p+on+1,cmp);
for(int i=1;i<=on;++i){
a1=p[i].u,a2=p[i].v,a3=p[i].w;
int f1=find(a1),f2=find(a2);
if(f1==f2)continue;
ff[f1]=f2;
_add(a1,a2,a3);_add(a2,a1,a3);
//if(amt==n-Q+1)break;
}
}
int fa[maxn][50],mn[maxn][50],dep[maxn];
//mn contain this now
//fa start from the last one
void Run(int u){
for(int i=1;(1<<i)<=dep[u];++i){
fa[u][i]=fa[fa[u][i-1]][i-1];
mn[u][i]=min(mn[u][i-1],mn[fa[u][i-1]][i-1]);
}
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].v;
if(!dep[v]){
dep[v]=dep[u]+1;
fa[v][0]=u;mn[v][0]=e[i].w;
Run(v);
}
}

}
inline int get(int a,int b){
if(dep[a]<dep[b])swap(a,b);
int gap=dep[a]-dep[b];
int ret=INF;
for(int i=0;(1<<i)<=gap;++i){
if(gap&(1<<i)){
ret=min(ret,mn[a][i]);
a=fa[a][i];    
}
}
if(a==b)return ret;
for(int i=18;i>=0;--i){
if(fa[a][i]!=fa[b][i]){
ret=min(ret,min(mn[a][i],mn[b][i]));
a=fa[a][i],b=fa[b][i];
}
}
return min(ret,min(mn[a][0],mn[b][0]));    
}
int limit[maxn];
int f[maxn];
int ans[maxn],top=0;
signed main(){
scanf("%lld%lld%lld",&n,&m,&Q);
for(int re i=1;i<=n;++i)scanf("%lld",&ord[i]);
for(int re i=1;i<=n;++i)scanf("%lld",&limit[i]);
for(int re i=1;i<=m;++i){
scanf("%lld%lld%lld",&a1,&a2,&a3);
p[i]=(pi){a1,a2,a3};
}

for(int re i=1;i<=Q;++i){
scanf("%lld",&a1);
col[a1]=1;
}
//    for(int re i=1;i<=n;++i){
//    p[i].u=col[p[i].u],p[i].v=col[p[i].v];
//    }
on=m;
if(Q){
for(int i=1;i<=n;++i){
if(a1==i||col[i]==0)continue;
p[++on]=(pi){a1,i,INF};
}
}
build();
dep[1]=1;
//for(int i=0;i<=19;++i)mn[1][i]=1000000009;
Run(1);
//    cerr<<mn[2][0]<<endl;
//    for(int u=1;u<=n;++u){
//    for(int i=head[u];i;i=e[i].nxt){
//    int v=e[i].v;
//    cerr<<u<<" &quo