#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef long double db;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<db,db> pdb;
typedef tuple<int,int,int> tii;
typedef tuple<ll,ll,ll> tll;
typedef tuple<int,int,int,int> ti4;
typedef vector<vector<ll>> mat;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
uniform_int_distribution<> gen(1,100); //gen(rng)
ll modinv(ll a,ll m){
if(m==1) return 0;
a%=m;
if(a<0) a+=m;
if(a==1) return 1;
return m-modinv(m,a)*m/a;
}
template <int MOD_> struct modnum{
private:
int v;
public:
static const int MOD = MOD_;
modnum() : v(0) {}
modnum(ll v_) : v(int(v_ % MOD)) { if (v < 0) v += MOD; }
explicit operator int () const { return v; }
friend bool operator == (const modnum& a, const modnum& b) { return a.v == b.v; }
friend bool operator != (const modnum& a, const modnum& b) { return a.v != b.v; }
friend bool operator < (const modnum& a, const modnum& b) { return a.v < b.v; }
friend bool operator <= (const modnum& a, const modnum& b) { return a.v <= b.v; }
friend bool operator > (const modnum& a, const modnum& b) { return a.v > b.v; }
friend bool operator >= (const modnum& a, const modnum& b) { return a.v >= b.v; }
modnum operator ~ () const {
modnum res;
res.v = modinv(v, MOD);
return res;
}
modnum& operator += (const modnum& o) {
v += o.v;
if (v >= MOD) v -= MOD;
return *this;
}
modnum& operator -= (const modnum& o) {
v -= o.v;
if (v < 0) v += MOD;
return *this;
}
modnum& operator *= (const modnum& o) {
v = int(ll(v) * ll(o.v) % MOD);
return *this;
}
modnum& operator /= (const modnum& o) {
return *this *= (~o);
}
modnum operator-() const { return modnum(-v); }
modnum& operator++() { return *this += 1; }
modnum operator++(int){ modnum tmp=*this; ++*this; return tmp; }
modnum& operator--() { return *this -= 1; }
modnum operator--(int){ modnum tmp=*this; --*this; return tmp; }
friend modnum operator + (const modnum& a, const modnum& b) { return modnum(a) += b; }
friend modnum operator - (const modnum& a, const modnum& b) { return modnum(a) -= b; }
friend modnum operator * (const modnum& a, const modnum& b) { return modnum(a) *= b; }
friend modnum operator / (const modnum& a, const modnum& b) { return modnum(a) /= b; }
friend modnum pow(modnum a, ll p) {
modnum ans = 1;
for (; p; p /= 2, a *= a) if (p&1) ans *= a;
return ans;
}
friend ostream& operator<<(std::ostream& os, const modnum& o)
{
os << o.v;
return os;
}
friend istream& operator>>(std::istream& is, modnum& o)
{
is >> o.v;
return is;
}
};
using mi=modnum<998244353>;
const ll mod=1e9+7,inf=1e18;
const int N=5e5+5,M=35,K=1e7+5;
int n,m,k,deg[N],in[N],out[N],cnt,h[N],p[17][N],mx[17][N];
pii arr[N];
tii e[N],e2[N];
ll ans,cur;
vector<pii> g[N],E[N];
struct UF{
int p[N]={0};
int Fi(int x){
if(!p[x]) return x;
return p[x]=Fi(p[x]);
}
bool Un(int x,int y){
x=Fi(x); y=Fi(y);
if(x==y) return false;
p[y]=x; return true;
}
}U;
void dfs(int u){
in[u]=++cnt;
for(auto [v,c] : g[u]) if(v!=p[0][u]){
h[v]=h[u]+1; p[0][v]=u; mx[0][v]=c; dfs(v);
}
out[u]=cnt;
}
int lca(int u,int v){
if(h[u]>h[v]) swap(u,v);
int d=h[v]-h[u];
for(int bit=16;bit>=0;bit--) if(d&(1<<bit)) v=p[bit][v];
if(u==v) return u;
for(int bit=16;bit>=0;bit--) if(p[bit][u]!=p[bit][v]){
u=p[bit][u]; v=p[bit][v];
}
return p[0][u];
}
int main(){
ios::sync_with_stdio(false); cin.tie(0);
cin>>n>>m;
for(int u,v,c,i=1;i<=m;i++){
cin>>u>>v>>c;
E[u].emplace_back(v,c);
E[v].emplace_back(u,c);
deg[u]++; deg[v]++;
e[i]=tii(c,u,v);
}
sort(e+1,e+1+m);
for(int i=1;i<=m;i++){
auto [c,u,v]=e[i];
if(!U.Un(u,v)) continue;
ans+=c;
g[u].emplace_back(v,c);
g[v].emplace_back(u,c);
}
dfs(1);
for(int bit=1;bit<17;bit++) for(int i=1;i<=n;i++){
p[bit][i]=p[bit-1][p[bit-1][i]];
mx[bit][i]=max(mx[bit-1][i],mx[bit-1][p[bit-1][i]]);
}
for(int i=1;i<=n;i++){
k=0;
arr[++k]=pii(in[i],i);
cur=ans;
for(auto [v,c] : E[i]){
arr[++k]=pii(in[v],v);
}
sort(arr+1,arr+1+k); assert(k==deg[i]+1);
for(int j=2;j<=deg[i]+1;j++){
int u=lca(arr[j-1].se,arr[j].se); arr[++k]=pii(in[u],u);
}
sort(arr+1,arr+1+k); k=unique(arr+1,arr+1+k)-arr-1;
for(int j=1;j<=k;j++) U.p[arr[j].se]=0;
for(auto [v,c] : E[i]){
assert(U.Un(i,v));
cur+=c;
}
stack<int> stk; stk.emplace(arr[1].se);
for(int j=2;j<=k;j++){
int u=arr[j].se;
while(in[u]<in[stk.top()]||out[stk.top()]<in[u]) stk.pop();
int val=0,d=h[u]-h[stk.top()],v=u;
for(int bit=16;bit>=0;bit--) if(d&&(1<<bit)){
val=max(val,mx[bit][v]); v=p[bit][v];
}
cur-=val;
e2[j-1]=tii(val,u,stk.top());
stk.emplace(u);
}
sort(e2+1,e2+k);
for(int j=1;j<k;j++){
auto [c,u,v]=e2[j];
if(!U.Un(u,v)) continue;
cur+=c;
}
for(int j=1;j<=k;j++) assert(U.Fi(arr[1].se)==U.Fi(arr[j].se));
cout<<cur<<"\n";
}
return 0;
}
Compilation message
LM.cpp: In function 'int main()':
LM.cpp:154:16: warning: unused variable 'c' [-Wunused-variable]
for(auto [v,c] : E[i]){
^
LM.cpp:172:41: warning: '<<' in boolean context, did you mean '<' ? [-Wint-in-bool-context]
for(int bit=16;bit>=0;bit--) if(d&&(1<<bit)){
~~^~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
22 ms |
24448 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
934 ms |
58276 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
