#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define x first
#define y second
#define ii pair<int,int>
int n,m,k;
vector<vector<int> >a;
const int M=1e5+7;
const int inf=1e9+7;
const int LOG=19;
int num_child[M],trace[M][LOG+10],l[M],fin[M],beg[M],num_node;
struct DSU
{
vector<int>sz,trace;
int n;
DSU(int _n=0)
{
n=_n;
sz.assign(n+7,1);
trace.resize(n+7);
iota(trace.begin(),trace.end(),0);
}
int get_dsu(int x)
{
return trace[x]==x?x:(trace[x]=get_dsu(trace[x]));
}
bool check(int x,int y)
{
int u=get_dsu(x);
int v=get_dsu(y);
return u==v;
}
bool get(int x,int y)
{
int u=get_dsu(x);
int v=get_dsu(y);
if(u==v)return true;
if(sz[u]>sz[v])swap(u,v);
trace[u]=v;
sz[v]+=sz[u];
return false;
}
};
struct node
{
int x,y,cost;
node(int _x=0,int _y=0,int _cost=0)
{
x=_x,y=_y,cost=_cost;
}
bool operator<(const node &a)const
{
return cost<a.cost;
}
};
void dfs(int x,int cha)
{
beg[x]=++num_node;
//cout<<x<<endl;
for(auto node:a[x])
{
if(node!=cha)
{
trace[node][0]=x;
l[node]=l[x]+1;
dfs(node,x);
num_child[x]+=num_child[node];
}
}
fin[x]=num_node;
}
void sprase(int n)
{
for(int i=1; i<=LOG; i++)
{
for(int node=1; node<=n; node++)
{
if(trace[node][i]!=-1)
{
trace[node][i]=trace[trace[node][i-1]][i-1];
}
}
}
}
int lca(int x,int y)
{
if(l[x]>l[y])swap(x,y);
int value=l[y]-l[x];
for(int i=LOG-1; i>=0; i--)
{
if(value&(1<<i))y=trace[y][i];
}
if(x==y)return x;
for(int i=LOG-1; i>=0; i--)
{
if(trace[x][i]!=trace[y][i])
{
x=trace[x][i];
y=trace[y][i];
}
}
}
struct BIT
{
vector<int>bit;
int n;
BIT(int _n=0)
{
n=_n;
bit.assign(n+7,0);
}
void update(int x,int value)
{
for(; x<=n; x+=x&(-x))
{
bit[x]+=value;
}
}
int get_sum(int x)
{
int ans=0;
for(;x;x-=x&(-x))
{
ans+=bit[x];
}
return ans;
}
void up(int x,int y,int value)
{
update(x,value);
if(y+1<=n)
{
update(y+1,-value);
}
}
};
int get_bit(int x,int y)
{
return x&(1<<y);
}
bool maximize(ll &a,ll b)
{
if(a<b)
{
a=b;
return true;
}
return false;
}
BIT tree;
int jump(int x)
{
int value=tree.get_sum(beg[x]);
for(int i=LOG-1; i>=0; i--)
{
//cout<<i<<" "<<trace[x][i]<<endl;
if(trace[x][i]==-1)continue;
if(tree.get_sum(trace[x][i])==value)
{
x=trace[x][i];
}
}
return x;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n,m,k;
cin>>n>>m>>k;
vector<node>e;
vector<int>color(n+1);
for(int i=1; i<=m; i++)
{
int x,y,cost;
cin>>x>>y>>cost;
e.push_back({x,y,cost});
}
vector<node>mst;
sort(e.begin(),e.end());
DSU s(n);
for(auto node:e)
{
if(!s.get(node.x,node.y))
{
mst.push_back({node.x,node.y,node.cost});
}
}
s=DSU(n);
vector<ii>edge;
for(int i=1; i<=k; i++)
{
int x,y;
cin>>x>>y;
edge.push_back(make_pair(x,y));
s.get(x,y);
}
vector<node>need,basic;
for(auto node:mst)
{
if(!s.get(node.x,node.y))
{
need.push_back({node.x,node.y,node.cost});
}
else basic.push_back({node.x,node.y,node.cost});
}
for(int i=1; i<=n; i++)
{
cin>>color[i];
}
s=DSU(n);
for(auto node:need)
{
s.get(node.x,node.y);
}
vector<int>index(n+1);
int cnt=0;
for(int i=1; i<=n; i++)
{
if(s.get_dsu(i)!=i)continue;
index[i]=++cnt;
}
for(int i=1; i<=n; i++)
{
index[i]=index[s.get_dsu(i)];
}
vector<int>sum(cnt+1,0);
for(int i=1; i<=n; i++)
{
sum[index[i]]+=color[i];
}
a.resize(cnt+7);
int sz=(int)basic.size();
ll kq=0;
for(int mask=0; mask<(1<<k); mask++)
{
bool check=true;
s=DSU(cnt);
memset(trace,-1,sizeof(trace));
vector<bool>check_edge(sz,false);
for(int i=1; i<=cnt; i++)
{
a[i].clear();
num_child[i]=sum[i];
}
for(int i=0; i<k; i++)
{
if(!get_bit(mask,i))continue;
ii res=edge[i];
int u=index[res.x];
int v=index[res.y];
if(s.check(u,v))
{
check=false;
break;
}
s.get(u,v);
//cout<<u<<" "<<v<<"-----"<<endl;
a[u].push_back(v);
a[v].push_back(u);
}
if(!check)continue;
for(int i=0; i<sz; i++)
{
node res=basic[i];
int u=index[res.x];
int v=index[res.y];
if(s.check(u,v))continue;
else
{
s.get(u,v);
check_edge[i]=true;
a[u].push_back(v);
a[v].push_back(u);
}
}
//cout<<mask<<endl;
num_node=0;
dfs(index[1],0);
//cout<<num_node<<endl;
sprase(cnt);
tree=BIT(cnt);
for(int i=2; i<=cnt; i++)
{
//cout<<beg[i]<<" "<<fin[i]<<endl;
tree.up(beg[i],fin[i],1);
}
vector<int>cp(cnt+1);
for(int i=0; i<sz; i++)
{
if(!check_edge[i])continue;
node res=basic[i];
int u=index[res.x];
int v=index[res.y];
if(trace[v][0]==u)swap(u,v);
tree.up(beg[u],fin[u],-1);
cp[u]=0;
}
// cout<<lca(1,2)<<endl;;
for(int i=0; i<sz; i++)
{
if(check_edge[i])continue;
node res=basic[i];
int u=index[res.x];
int v=index[res.y];
int new_lca=lca(u,v);
int cost=res.cost;
//cout<<u<<" "<<v<<" "<<new_lca<<" "<<mask<<endl;
for(u=jump(u);l[u]>l[new_lca]; u=jump(u))
{
//cout<<u<<endl;
cp[u]=cost;
tree.up(beg[u],fin[u],-1);
}
for(v=jump(v);l[v]>l[new_lca];v=jump(v))
{
cp[v]=cost;
tree.up(beg[v],fin[v],-1);
}
}
ll ans=0;
for(int i=1; i<=cnt; i++)
{
ans+=1LL*cp[i]*num_child[i];
}
maximize(kq,ans);
}
cout<<kq;
}
Compilation message
toll.cpp: In function 'int lca(int, int)':
toll.cpp:103:1: warning: control reaches end of non-void function [-Wreturn-type]
103 | }
| ^
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
7 ms |
11596 KB |
Output is correct |
| 2 |
Correct |
7 ms |
11596 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
7 ms |
11596 KB |
Output is correct |
| 2 |
Correct |
7 ms |
11596 KB |
Output is correct |
| 3 |
Execution timed out |
2575 ms |
11652 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
7 ms |
11596 KB |
Output is correct |
| 2 |
Correct |
7 ms |
11596 KB |
Output is correct |
| 3 |
Execution timed out |
2575 ms |
11652 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
7 ms |
11596 KB |
Output is correct |
| 2 |
Correct |
7 ms |
11596 KB |
Output is correct |
| 3 |
Execution timed out |
2575 ms |
11652 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
7 ms |
11596 KB |
Output is correct |
| 2 |
Correct |
7 ms |
11596 KB |
Output is correct |
| 3 |
Execution timed out |
2575 ms |
11652 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
