为什么这样过了↓
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
const int N=1e5+5;
ll n,k,f[N];
ll ans=0;
bool ofa[4*N];//occupy from army
struct road
{
int from,to;
ll way;
bool operator<(const road &x)const
{
return way>x.way;
}
}s[4*N];
inline ll read()
{
ll r=0,f=1;
char c=getchar();
while(c<'0'||c>'9')
{
if(c=='-') f=-f;
c=getchar();
}
while(c>='0'&&c<='9')
{
r=(r<<1)+(r<<3)+(c^48);
c=getchar();
}
return r*f;
}
inline void write(ll x)
{
if(x<0) putchar('-'),x=-x;
if(x>=10) write(x/10);
putchar(x%10+'0');
}
inline ll find(ll x)
{
if(f[x]==x) return x;
return f[x]=find(f[x]);
}
signed main()
{
n=read();k=read();
for(register int i=1;i<=n;++i)
f[i]=i;
for(register int i=1;i<=k;++i)
{
ll x=read();
ofa[x]=true;
}
for(register int i=1;i<=n-1;++i)
{
s[i].from=read();
s[i].to=read();
s[i].way=read();
ans+=s[i].way;
}
// cout<<ans<<endl;
sort(s+1,s+1+n);
for(register int i=1;i<=n-1;++i)
{
int a=s[i].from,b=s[i].to;
int fa=find(a),fb=find(b);
if(ofa[fa]&&ofa[fb])
continue;
f[fa]=fb;
ans-=s[i].way;
if(ofa[fa]) ofa[fb]=true;
else ofa[fa]=true;
// ofa[fa]=true;
// ofa[fb]=true;
}
write(ans);
return 0;
}
而这样↓就不行
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
const int N=1e5+5;
ll n,k,f[N];
ll ans=0;
bool ofa[4*N];//occupy from army
struct road
{
int from,to;
ll way;
bool operator<(const road &x)const
{
return way>x.way;
}
}s[4*N];
inline ll read()
{
ll r=0,f=1;
char c=getchar();
while(c<'0'||c>'9')
{
if(c=='-') f=-f;
c=getchar();
}
while(c>='0'&&c<='9')
{
r=(r<<1)+(r<<3)+(c^48);
c=getchar();
}
return r*f;
}
inline void write(ll x)
{
if(x<0) putchar('-'),x=-x;
if(x>=10) write(x/10);
putchar(x%10+'0');
}
inline ll find(ll x)
{
if(f[x]==x) return x;
return f[x]=find(f[x]);
}
signed main()
{
n=read();k=read();
for(register int i=1;i<=n;++i)
f[i]=i;
for(register int i=1;i<=k;++i)
{
ll x=read();
ofa[x]=true;
}
for(register int i=1;i<=n-1;++i)
{
s[i].from=read();
s[i].to=read();
s[i].way=read();
ans+=s[i].way;
}
// cout<<ans<<endl;
sort(s+1,s+1+n);
for(register int i=1;i<=n-1;++i)
{
int a=s[i].from,b=s[i].to;
int fa=find(a),fb=find(b);
if(ofa[fa]&&ofa[fb])
continue;
f[fa]=fb;
ans-=s[i].way;
// if(ofa[fa]) ofa[fb]=true;
// else ofa[fa]=true;
ofa[fa]=true;
ofa[fb]=true;
}
write(ans);
return 0;
}