#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int , int> pii; const int maxN = int(3e5)+7; const int maxM = int(3e5)+7; const int maxK = 21; struct edge{ int u , v , w; edge(){}; edge(int _u , int _v , int _w){ u = _u; v = _v; w = _w; } bool operator < (const edge& other) const{ return w < other.w; } }; struct DSU{ int n , fa[maxN]; void init(int _n){ n = _n; for (int i = 1 ; i <= n ; i++) fa[i] = -1; } int root(int x){ if (fa[x] < 0) return x; else return fa[x] = root(fa[x]); } void unite(int u , int v){ u = root(u); v = root(v); if (u == v) return; if (-fa[u] < -fa[v]) swap(u , v); fa[u] += fa[v]; fa[v] = u; } } dsu; int n , m , k , p[maxN]; edge E[maxM]; vector<pii> g[maxN]; pii greedy[maxK]; int del[maxK]; int get(int u , int par , int en){ for (pii e : g[u]){ int v = e.first; int id = e.second; if (v == par) continue; if (v == en) return id; int tmp = get(v , u , en); if (tmp != -1) return max(tmp , id); } return -1; } bool del_edge[maxN]; ll cost[maxN] , sz[maxN]; vector<pii> adj[maxN]; bool ok[maxK]; void dfs(int u , int par , ll &ans){ sz[u] = cost[u]; for (pii e : adj[u]){ int v = e.first; int id = e.second; int w = E[del[id]].w; if (v == par) continue; dfs(v , u , ans); if (ok[id]) ans += 1ll * sz[v] * w; sz[u] += sz[v]; } } void solve(){ cin >> n >> m >> k; //assert(k == 1); for (int i = 1 ; i <= m ; i++){ int u , v , w; cin >> u >> v >> w; E[i] = edge(u , v , w); } sort(E + 1 , E + m + 1); dsu.init(n); for (int i = 1 ; i <= m ; i++){ int u = E[i].u; int v = E[i].v; int w = E[i].w; if (dsu.root(u) != dsu.root(v)){ dsu.unite(u , v); g[u].push_back({v , i}); g[v].push_back({u , i}); } else{ del_edge[i] = 1; } } for (int i = 0 ; i < k ; i++){ int u , v; cin >> u >> v; greedy[i] = {u , v}; del[i] = get(u , 0 , v); del_edge[del[i]] = 1; } dsu.init(n); for (int i = 1 ; i <= m ; i++){ if (del_edge[i] == 1) continue; int u = E[i].u; int v = E[i].v; dsu.unite(u , v); } for (int i = 1 ; i <= n ; i++) cin >> p[i]; vector<int> ver; for (int i = 1 ; i <= n ; i++){ if (dsu.root(i) == i) ver.push_back(i); cost[dsu.root(i)] += 1ll * p[i]; } ll ans = 0; for (int mask = 0 ; mask < (1<<k) ; mask++){ for (int x : ver){ adj[x].clear(); } for (int i = 0 ; i < k ; i++){ int u = ((mask>>i)&1) ? greedy[i].first : E[del[i]].u; int v = ((mask>>i)&1) ? greedy[i].second : E[del[i]].v; u = dsu.root(u); v = dsu.root(v); int w = E[del[i]].w; adj[u].push_back({v , i}); adj[v].push_back({u , i}); ok[i] = ((mask>>i)&1); } ll cur_ans = 0; dfs(dsu.root(1) , 0 , cur_ans); ans = max(ans , cur_ans); } cout << ans << "\n"; } int main(){ if (fopen("D.inp" , "r")){ freopen("D.inp" , "r" , stdin); freopen("D.out" , "w" , stdout); } ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int numTest = 1; //cin >> numTest; while (numTest--) solve(); return 0; }

toll.cpp: In function 'int main()':
toll.cpp:153:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  153 |         freopen("D.inp" , "r" , stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
toll.cpp:154:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  154 |         freopen("D.out" , "w" , stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~