結果

問題 No.1637 Easy Tree Query
ユーザー Nzt3
提出日時 2021-08-06 21:53:14
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 297 ms / 2,000 ms
コード長 874 bytes
コンパイル時間 1,973 ms
コンパイル使用メモリ 184,652 KB
実行使用メモリ 11,256 KB
最終ジャッジ日時 2024-09-17 03:50:21
合計ジャッジ時間 9,711 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 33
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;
int main(){
  int N,Q;
  cin>>N>>Q;
  vector<vector<int>>G(N);
  for(int i=0,a,b;i<N-1;i++){
    cin>>a>>b;
    --a,--b;
    G[a].push_back(b);
    G[b].push_back(a);
  }
  vector<array<int,2>>dist(N);
  for(int i=0;i<N;i++){
    dist[i]={1000000,i};
  }
  dist[0][0]=0;
  queue<int>bfs;
  bfs.push(0);
  while(bfs.size()){
    int t=bfs.front();
    bfs.pop();
    for(int i:G[t]){
      if(dist[i][0]>dist[t][0]+1){
        dist[i][0]=dist[t][0]+1;
        bfs.push(i);
      }
    }
  }
  auto dist2=dist;
  sort(dist.begin(),dist.end(),greater<array<int,2>>());
  vector<long long>sz(N,1);
  for(int i=0;i<N;i++){
    for(int j:G[dist[i][1]]){
      if(dist2[j][0]<dist[i][0]){
        sz[j]+=sz[dist[i][1]];
      }
    }
  }
  long long ans=0,x,p;
  while(Q--){
    cin>>p>>x;
    ans+=x*sz[p-1];
    cout<<ans<<'\n';
  }
}
0