Submission #968757

---

Source Code Expand

#include<bits/stdc++.h>
#define REP(i,m) for(int i=0;i<(m);++i)
#define REPN(i,m,in) for(int i=(in);i<(m);++i)
#define ALL(t) (t).begin(),(t).end()
#define CLR(a) memset((a),0,sizeof(a))
#define pb push_back
#define mp make_pair
#define fr first
#define sc second

using namespace std;


#ifdef DEB
#define dump(x)  cerr << #x << " = " << (x) << endl
#define prl cerr<<"called:"<< __LINE__<<endl
#define dumpR(x) cerr<<"\x1b[31m"<<#x<<" = " <<(x)<<"\x1b[39m"<<endl
#define dumpY(x) cerr<<"\x1b[33m"<<#x<<" = " <<(x)<<"\x1b[39m"<<endl
#define dumpG(x) cerr<<"\x1b[32m"<<#x<<" = " <<(x)<<"\x1b[39m"<<endl
template<class T> void debug(T a,T b){ for(;a!=b;++a) cerr<<*a<<' ';cerr<<endl;}
#else
#define dump(x) ;
#define dumpR(x) ;
#define dumpY(x) ;
#define dumpG(x) ;
#define prl ;
template<class T> void debug(T a,T b){ ;}
#endif

template<class T> void chmin(T& a,const T& b) { if(a>b) a=b; }
template<class T> void chmax(T& a,const T& b) { if(a<b) a=b; }

typedef long long int lint;
typedef pair<lint,lint> pi;

namespace std{
  template<class S,class T>
  ostream &operator <<(ostream& out,const pair<S,T>& a){
    out<<'('<<a.fr<<','<<a.sc<<')';
    return out;
  }
}

const int INF=5e8;
int n,X;
vector<pi> g[100005];


static const int MAXN=100005;
int cut[MAXN],size[MAXN],whole;
int root,rcost;
int getsize(int v,int p){
  size[v]=1;
  REP(i,g[v].size()){
    int to=g[v][i].fr;
    if(to!=p && cut[to]==0) size[v]+=getsize(to,v);
  }
  return size[v];
}
void getbestroot(int v,int p){
  int maxi=0;
  REP(i,g[v].size()){
    int to=g[v][i].fr;
    if(to!=p && cut[to]==0){
      getbestroot(to,v);
      maxi=max(maxi,size[to]);
    }
  }
  int rest=whole-size[v];
  maxi=max(maxi,rest);
  if(maxi<rcost){
    rcost=maxi;
    root=v;
  }
}
struct BIT{
  lint val[MAXN*2+2];
  int n;
  void init(int n_){
    n=1;
    while(n<n_) n<<=1;
    REP(i,n+1) val[i]=0;
  }
  void add(int k,int a){
    chmin(k,n);
    chmax(k,0);
    ++k;
    while(k<=n){
      val[k]+=a;
      k+=k&-k;
    }
  }
  int query(int k){ //[0,k)
    chmin(k,n);
    chmax(k,0);
    int res=0;
    while(k>0){
      res+=val[k];
      k-=k&-k;
    }
    return res;
  }
};

BIT bit,sum;


lint ans,incnt;
lint dfs2(int v,int p,int len){
  chmin(len,X+2);
  lint res=bit.query(X-len+1);
  ans+=sum.query(X-len+1)+res*len;
  dumpG(v);
  dump(res);dump(sum.query(X-len+1)+res*len);
  for(auto e:g[v]){
    if(e.fr==p || cut[e.fr]) continue;
    res+=dfs2(e.fr,v,len+e.sc);
  }
  return res;
}
void dfs3(int v,int p,int len,int sign){
  chmin(len,X+2);
  bit.add(len,sign);
  sum.add(len,len*sign);
  for(auto e:g[v]){
    if(e.fr==p || cut[e.fr]) continue;
    dfs3(e.fr,v,len+e.sc,sign);
  }
}

void dfs(int v){
  getsize(v,-1);
  if(size[v]==1) return;
  whole=size[v];
  rcost=INF;
  getbestroot(v,-1);
  v=root;

  lint res=0;
  cut[v]=1;
  REP(i,g[v].size()){
    int to=g[v][i].fr;
    if(cut[to]==0) dfs(to);
  }

  dumpR(v);
  bit.add(0,1);
  REP(i,g[v].size()){
    pi& e=g[v][i];
    if(cut[e.fr]==0){
      res+=dfs2(e.fr,v,e.sc);
      dfs3(e.fr,v,e.sc,1);
    }
  }

  bit.add(0,-1);
  REP(i,g[v].size()){
    pi& e=g[v][i];
    if(cut[e.fr]==0){
      dfs3(e.fr,v,e.sc,-1);
    }
  }
  cut[v]=0;
  incnt+=res;
  dump(incnt);
}


lint mini[100005],mxi[100005];
const lint INF2=1e18;
void rec(int v,int p){
  mini[v]=INF2;
  mxi[v]=0;
  for(auto e:g[v]){
    if(e.fr==p) continue;
    rec(e.fr,v);
    chmin(mini[v],e.sc);
    chmax(mxi[v],mxi[e.fr]+1);
  }
}
lint min_top[100005],max_top[100005];
int par[100005];

pi min1[100005],min2[100005],max1[100005],max2[100005];
void rec2(int v,int p){
  par[v]=p;
  pi min1={min_top[v],-1},min2={INF2,-1},max1={max_top[v],-1},max2={-1,-1};
  for(auto e:g[v]){
    if(e.fr==p) continue;
    pi mn=mp(e.sc,e.fr);
    pi mx=mp(mxi[e.fr]+1,e.fr);
    if(min1>mn){
      min2=min1;
      min1=mn;
    }else if(min2>mn) min2=mn;

    if(max1<mx){
      max2=max1;
      max1=mx;
    }else if(max2<mx) max2=mx;
  }
  ::min1[v]=min1;
  ::min2[v]=min2;
  ::max1[v]=max1;
  ::max2[v]=max2;
  dump(v);dump(min1);dump(min2);
  for(auto e:g[v]){
    if(e.fr==p) continue;
    if(e.fr==min1.sc) min_top[e.fr]=min2.fr+e.sc;
    else min_top[e.fr]=min1.fr+e.sc;

    if(e.fr==max1.sc) max_top[e.fr]=max2.fr+1;
    else max_top[e.fr]=max1.fr+1;
    rec2(e.fr,v);
  }
}

pi get(int a,int b){
  if(par[a]==b){
    return mp(mini[a],mxi[a]);
  }else{
    pi res;
    if(min1[a].sc==b) res.fr=min2[a].fr;
    else res.fr=min1[a].fr;
    if(max1[a].sc==b) res.sc=max2[a].fr;
    else res.sc=max1[a].fr;
    return res;
  }
}
int calc(pi a){
  return min(a.fr+X,(a.sc>=2?X:INF)+(lint)X);
}


int main(){
  cin>>n>>X;
  bit.init(X+3);
  sum.init(X+3);

  lint dif=0;
  vector<pair<pi,int> >es;
  REP(i,n-1){
    int a,b,c;scanf("%d%d%d",&a,&b,&c);--a;--b;

    if(c>X){
      es.pb(mp(mp(a,b),c));
    }
    g[a].pb(mp(b,c));
    g[b].pb(mp(a,c));
  }
  if(n==2){
    cout<<g[0][0].sc<<endl;
    return 0;
  }
  if(es.size()>0){
    rec(0,-1);
    max_top[0]=-1;
    min_top[0]=INF2;
    rec2(0,-1);
    for(auto e:es){
      int a=e.fr.fr,b=e.fr.sc,c=e.sc;

      pi A=get(a,b),B=get(b,a);
      dump(A);dump(B);
      dif+=min({calc(A),calc(B),c})-X;
    }
    debug(ALL(es));
    dump(dif);
  }

  dfs(0);

  dump(ans);dump(incnt);
  lint res=ans+(n*(lint)(n-1)/2-incnt)*X;
  res+=dif;
  cout<<res<<endl;
  return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:244:39: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     int a,b,c;scanf("%d%d%d",&a,&b,&c);--a;--b;
                                       ^

Judge Result