제출 #1007363

#제출 시각아이디문제언어결과실행 시간메모리
1007363AdamGSDesignated Cities (JOI19_designated_cities)C++17
7 / 100
115 ms33876 KiB
#include<bits/stdc++.h>
using namespace std;
typedef long double ld;
typedef long long ll;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const int LIM=2e5+7;
vector<pair<ll,ll>>V[LIM];
ll wynik[LIM], sum;
void DFS(int x, int o) {
  for(auto i : V[x]) if(i.st==o) sum+=i.nd; else DFS(i.st, x);
}
void DFS2(int x, int o) {
  for(auto i : V[x]) if(i.st==o) sum-=i.nd;
  wynik[1]=max(wynik[1], sum);
  for(auto i : V[x]) if(i.st!=o) {
    sum+=i.nd;
    DFS2(i.st, x);
    sum-=i.nd;
  }
  for(auto i : V[x]) if(i.st==o) sum+=i.nd;
}
int main() {
  ios_base::sync_with_stdio(0); cin.tie(0);
  int n;
  cin >> n;
  ll summ=0;
  rep(i, n-1) {
    ll a, b, c, d;
    cin >> a >> b >> c >> d; --a; --b;
    V[a].pb({b, c});
    V[b].pb({a, d});
    summ+=c+d;
  }
  DFS(0, 0);
  DFS2(0, 0);
  rep(i, n+1) wynik[i]=summ-wynik[i];
  int q;
  cin >> q;
  while(q--) {
    int x;
    cin >> x;
    cout << wynik[x] << '\n';
  }
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...