結果

問題 No.386 貪欲な領主
ユーザー planesplanes
提出日時 2022-09-15 19:49:51
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 416 ms / 2,000 ms
コード長 2,037 bytes
コンパイル時間 1,801 ms
コンパイル使用メモリ 179,700 KB
実行使用メモリ 31,620 KB
最終ジャッジ日時 2023-08-22 14:30:09
合計ジャッジ時間 4,710 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,376 KB
testcase_01 AC 2 ms
4,376 KB
testcase_02 AC 2 ms
4,380 KB
testcase_03 AC 2 ms
4,380 KB
testcase_04 AC 416 ms
31,572 KB
testcase_05 AC 294 ms
28,660 KB
testcase_06 AC 300 ms
28,392 KB
testcase_07 AC 4 ms
4,380 KB
testcase_08 AC 35 ms
5,368 KB
testcase_09 AC 5 ms
4,376 KB
testcase_10 AC 1 ms
4,376 KB
testcase_11 AC 2 ms
4,384 KB
testcase_12 AC 3 ms
4,380 KB
testcase_13 AC 8 ms
4,376 KB
testcase_14 AC 304 ms
28,468 KB
testcase_15 AC 379 ms
31,620 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

 #include <bits/stdc++.h> 
using namespace std;
using ll =long long;
#define all(v) v.begin(),v.end()
 #define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)

ll INF=2e18;


struct LCA {

ll V;
ll logV;
vector<vector<ll>> G;
ll root;
vector<vector<ll>> parent;//いないなら-1
vector<ll> depth;


//コンストラクタ
LCA(ll V_) :V(V_) {
  root=0;
   ll k=1;
   logV=0;
   while(k<=V) {
      k*=2;
      logV++;
   }

   G=vector<vector<ll>> (V,vector<ll> (0));
   parent=vector<vector<ll>> (V,vector<ll> (logV,-1));
   depth=vector<ll> (V);

}


void dfs(ll v,ll p,ll d) {
   parent[v][0]=p;
   depth[v]=d;
   for(ll i=0;i<G[v].size();i++) {
if(G[v][i]!=p) dfs(G[v][i],v,d+1);
   }
}

void init() {
   dfs(root,-1,0);
   for(ll k=0;k+1<logV;k++) {
      for(ll v=0;v<V;v++) {
         if(parent[v][k]<0) parent[v][k+1]=-1;
         else parent[v][k+1]=parent[parent[v][k]][k];
      }
   }
}

ll lca(ll u,ll v) {
   if(depth[u]>depth[v]) swap(u,v);
   for(ll k=0;k<logV;k++) {
      if(((depth[v]-depth[u])>>k)&1) {
         v=parent[v][k];
      }
   }

   if(u==v) return u;

   for(ll k=logV-1;k>=0;k--) {
      if(parent[u][k]!=parent[v][k]) {
         u=parent[u][k];
         v=parent[v][k];
      }
   }
   return parent[u][0];
}

};


int main() {
    ll N;cin>>N;
     
     LCA p(N);
     for(ll i=0;i<N-1;i++) {
        ll a,b;cin>>a>>b;
        p.G[a].push_back(b);
        p.G[b].push_back(a);
     }
     p.init();
     

     vector<ll> U(N);
     for(ll i=0;i<N;i++) cin>>U[i];

     vector<ll> d(N,INF);
     queue<pair<ll,ll>> S;
    S.push({0,0});

    while(!S.empty()) {
        auto x=S.front();
        S.pop();
        if(d[x.first]!=INF) continue;
        d[x.first]=x.second+U[x.first];
    
    for(auto y:p.G[x.first]) {
        S.push({y,d[x.first]});
    }
    }


    ll M;cin>>M;
    ll ans=0;

    for(ll i=0;i<M;i++) {
        ll A,B,C;cin>>A>>B>>C;
        ll k=p.lca(A,B);
        ll count=d[A]+d[B]-2*d[k]+U[k];
        ans+=count*C;
    }

    cout<<ans<<endl;

}
0