Pagini recente » Cod sursa (job #3224033) | Cod sursa (job #1123617) | Cod sursa (job #2543552) | Cod sursa (job #1605569) | Cod sursa (job #1925705)
#include <fstream>
#include <algorithm>
#include <vector>
#define x first
#define y second
using namespace std;
ifstream f("trumplandia.in"); ofstream g("trumplandia.out");
int n,m,q;
struct art {int x,y,c,d,viz;} a[200010],sol[200010];
long long facut[200010];
int T[32][200010],Lev[200010];
int viz[200010],inv[200010],GR[200010];
vector <pair<int,int> > G[2*200010];
int grupa(int i)
{ if (GR[i] == i) return i;
GR[i] = grupa(GR[i]);
return GR[i];
}
void reuniune(int i,int j)
{ GR[grupa(i)]=grupa(j);}
int cmp(art h, art l)
{ if(h.c<l.c) return 1;
return 0;
}
int lca(int x, int y)
{
if(Lev[x] < Lev[y])
swap(x, y);
int log1, log2;
for(log1 = 1; (1 << log1) < Lev[x]; ++log1);
for(log2 = 1; (1 << log2) < Lev[y]; ++log2);
for(int k = log1; k >= 0; --k)
if(Lev[x] - (1 << k) >= Lev[y])
x = T[k][x];
if(x == y) return x;
for(int k = log2; k >= 0; --k)
if(T[k][x] && T[k][x] != T[k][y])
x = T[k][x],
y = T[k][y];
return T[0][x];
}
void dfs(int nod, int lev)
{ Lev[nod]=lev; viz[nod]=1;
vector <pair<int,int> > :: iterator it=G[nod].begin(),sf=G[nod].end();
for(; it!=sf; it++)
if(viz[(*it).x]==0) {T[0][(*it).x]=nod; dfs((*it).x, lev+1);}
}
int main()
{ f>>n>>m>>q;
for(int i=1; i<=m; i++) {f>>a[i].x>>a[i].y>>a[i].c; a[i].d=i;}
for(int i = 1;i <= n; ++i) GR[i]=i;
sort(a+1,a+m+1,cmp);
for(int i=1; i<=m; i++) inv[a[i].d]=i;
long long ct=0,k=0;
for(int i = 1;i <= m; ++i)
if(grupa(a[i].x)!=grupa(a[i].y))
{ ct=1LL*(ct+a[i].c);
a[i].viz=1;
sol[++k]=a[i];
reuniune(a[i].x,a[i].y);
}
for(int i=1; i<=k; i++)
{ G[sol[i].x].push_back(make_pair(sol[i].y,sol[i].c));
G[sol[i].y].push_back(make_pair(sol[i].x,sol[i].c));
}
dfs(1,0);
g<<ct<<'\n';
for(k = 1; (1 << k) <= n; ++k)
for(int i = 1; i <= n; ++i)
T[k][i] = T[k-1][T[k-1][i]];
for(int mc,i=1; i<=q; i++)
{ f>>mc;
int leg=inv[mc];
if(a[leg].viz==1) g<<ct<<'\n';
else
{ if(facut[leg]!=0) g<<facut[leg]<<'\n';
else
{ int lc=lca(a[leg].x,a[leg].y);
int cur=a[leg].x;
int vmax=0;
for(int k=0; (1<<k)<=n; ++k)
while(T[k][cur]!=0 and cur!=lc)
{ vector<pair<int,int> > :: iterator it=G[cur].begin(), sf=G[cur].end();
for(; it!=sf; it++)
if((*it).x==T[k][cur] and (*it).y>vmax) vmax=(*it).y;
cur=T[k][cur];
}
cur=a[leg].y;
for(int k=0; (1<<k)<=n; ++k)
while(T[k][cur]!=0 and cur!=lc)
{
vector<pair<int,int> > :: iterator it=G[cur].begin(), sf=G[cur].end();
for(; it!=sf; it++)
if((*it).x==T[k][cur] and (*it).y>vmax) vmax=(*it).y;
cur=T[k][cur];
}
facut[leg]=1LL*(ct-vmax+a[leg].c);
g<<facut[leg]<<'\n';
}
}
}
g.close(); return 0;
}