Submission #4352791

---

Source Code Expand

#include<iostream>
#include<string>
#include<vector>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<algorithm>
#include<functional>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cassert>
#include<ctime>
using namespace std;

#define mind(a,b) (a>b?b:a)
#define maxd(a,b) (a>b?a:b)
#define absd(x) (x<0?-(x):x)
#define pow2(x) ((x)*(x))
#define rep(i,n) for(int i=0; i<n; ++i)
#define repr(i,n) for(int i=n-1; i>=0; --i)
#define repl(i,s,n) for(int i=s; i<=n; ++i)
#define replr(i,s,n) for(int i=n; i>=s; --i)
#define repf(i,s,n,j) for(int i=s; i<=n; i+=j)
#define repe(e,obj) for(auto e : obj)

#define SP << " " <<
#define COL << " : " <<
#define COM << ", " <<
#define ARR << " -> " <<
#define PNT(STR) cout << STR << endl
#define POS(X,Y) "(" << X << ", " << Y << ")"
#define DEB(A) " (" << #A << ") " << A
#define DEBREP(i,n,val) for(int i=0; i<n; ++i) cout << val << " "; cout << endl
#define ALL(V) (V).begin(), (V).end()
#define INF 1000000007
#define INFLL 1000000000000000007LL
#define EPS 1e-9

typedef unsigned int uint;
typedef unsigned long ulong;
typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;
#define P_TYPE int
typedef pair<P_TYPE, P_TYPE> P;
typedef pair<P, P_TYPE> PI;
typedef pair<P_TYPE, P> IP;
typedef pair<P, P> PP;
typedef priority_queue<P, vector<P>, greater<P> > pvqueue;

#define LV 19
#define N 100005

int n;
vector<int> g[N];

int root;
vector<int> g0[N];
int parent[N], level[N];

bool c_used[N];
int sz[N];
int count_dfs(int v, int p) {
  int c = 1;
  repe(w, g[v]) {
    if(w == p || c_used[w]) continue;
    c += count_dfs(w, v);
  }
  return sz[v] = c;
}

int search_centroid(int v, int p, int s) {
  if((s - sz[v])*2 > s) {
    return -1;
  }
  bool ok = true;
  repe(w, g[v]) {
    if(w == p || c_used[w]) continue;

    int x = search_centroid(w, v, s);
    if(x != -1) {
      return x;
    }
    if(sz[w]*2 > s) {
      ok = false;
      break;
    }
  }
  return ok ? v : -1;
}

vector<P> gt[N];

void centroid() {
  queue<int> que;

  int s = count_dfs(0, -1);
  int x = search_centroid(0, -1, s);
  que.push(x);
  c_used[x] = true;
  root = x;
  parent[x] = -1;
  level[x] = 0;

  while(!que.empty()) {
    int v = que.front(); que.pop();
    repe(w, g[v]) {
      if(c_used[w]) {
        continue;
      }

      int s = count_dfs(w, -1);
      int x = search_centroid(w, -1, s);
      g0[v].push_back(x);
      parent[x] = v;
      level[x] = level[v] + 1;

      que.push(x);
      c_used[x] = true;
    }
  }
}

class LiChaoTree {
  int n;
  ll *xs, *p, *q;
  bool *u;

  void _add_line(ll a, ll b, int k, int l, int r) {
    while(r-l > 0) {
      int m = (l + r) >> 1;
      if(!u[k]) {
        p[k] = a; q[k] = b;
        u[k] = true;
        return;
      }

      ll lx = xs[l], mx = xs[m], rx = xs[r-1];
      ll pk = p[k], qk = q[k];
      bool left = (a*lx+b < pk*lx+qk);
      bool mid = (a*mx+b < pk*mx+qk);
      bool right = (a*rx+b < pk*rx+qk);
      if(left && right) {
        p[k] = a; q[k] = b;
        return;
      }
      if(!left && !right) {
        return;
      }
      if(mid) {
        swap(p[k], a);
        swap(q[k], b);
      }
      if(left != mid) {
        k = 2*k+1; r = m;
      } else {
        k = 2*k+2; l = m;
      }
    }
  }

  ll _query(int k, ll x) {
    k += n - 1;
    ll s = u[k] ? p[k]*x+q[k] : INFLL;
    while(k > 0) {
      k = (k - 1) / 2;
      if(u[k]) {
        ll r = p[k]*x+q[k];
        s = min(s, r);
      }
    }
    return s;
  }

public:
  LiChaoTree(const vector<int> &ps) {
    int n0 = ps.size();
    n = 1;
    while(n < n0) n <<= 1;

    xs = new ll[2*n];
    p = new ll[2*n];
    q = new ll[2*n];
    u = new bool[2*n];

    rep(i, 2*n) u[i] = false;
    rep(i, n0) xs[i] = ps[i];
    repl(i, n0, n-1) xs[i] = INF;
  }
  ~LiChaoTree() {
    delete xs;
    delete p;
    delete q;
    delete u;
  }

  void add_line(ll a, ll b) {
    _add_line(a, b, 0, 0, n);
  }

  void add_segment_line(ll a, ll b, int l, int r) {
    if(r == -1) r = n;
    ll l0 = l + n, r0 = r + n;
    ll s0 = l, t0 = r, sz = 1;
    while(l0 < r0) {
      if(r0 & 1) {
        --r0; t0 -= sz;
        _add_line(a, b, r0-1, t0, t0+sz);
      }
      if(l0 & 1) {
        _add_line(a, b, l0-1, s0, s0+sz);
        ++l0; s0 += sz;
      }
      l0 >>= 1; r0 >>= 1;
      sz <<= 1;
    }
  }

  ll query(int i) {
    return _query(i, xs[i]);
  }
};

map<int, int> compress(const vector<int> &xs) {
  map<int, int> result;
  for(int i=0; i<xs.size(); ++i) {
    result[xs[i]] = 0;
  }
  int i = 0;
  for(auto it = result.begin(); it != result.end(); ++it, ++i) {
    result[(*it).first] = i;
  }
  return result;
}

ll cost[LV][N], dist[LV][N];
ll vs[N], ls[N];
vector<int> vv[N];
ll res[N];
int used[N];
void solve() {
  centroid();
  rep(u, n) {
    vector<int> qs;
    set<int> ss;
    vector<int> ws;

    queue<int> que;
    int lv = level[u];
    que.push(u);
    cost[lv][u] = dist[lv][u] = 0;
    used[u] = u+1;
    ws.push_back(u);

    repe(i, vv[u]) {
      qs.push_back(i);
      ss.insert(ls[i]);
    }

    while(!que.empty()) {
      int v = que.front(); que.pop();
      ll dv = dist[lv][v], cv = cost[lv][v];
      repe(&p, gt[v]) {
        int w = p.first, c = p.second;
        if(level[w] < lv || used[w] == u+1) {
          continue;
        }
        cost[lv][w] = cv + c;
        dist[lv][w] = dv + 1;
        que.push(w);
        ws.push_back(w);
        used[w] = u+1;

        repe(i, vv[w]) {
          if(ls[i] - dist[lv][w] >= 0) {
            qs.push_back(i);
            ss.insert(ls[i] - dist[lv][w]);
          }
        }
      }
    }
    vector<int> xs;
    repe(x, ss) xs.push_back(x);
    map<int, int> comp = compress(xs);
    LiChaoTree lct(xs);

    vector<ll> rs;
    int cur = 0;
    rep(i, ws.size()) {
      ll w = ws[i], c = 0;
      ll d = dist[lv][w];
      while(cur < xs.size() && xs[cur] < d) {
        rs.push_back(lct.query(cur++));
      }
      repe(&p, gt[w]) {
        c = max(c, (ll)p.second);
      }
      lct.add_line(-c, -(cost[lv][w] - c*d));
    }
    while(cur < xs.size()) {
      rs.push_back(lct.query(cur++));
    }

    repe(i, qs) {
      ll x = ls[i] - dist[lv][vs[i]];
      ll r0 = cost[lv][vs[i]] - rs[comp[x]];
      res[i] = max(res[i], r0);
    }
  }
}

int main() {
  scanf("%d", &n);
  rep(i, n-1) {
    int a, b, c; scanf("%d %d %d", &a, &b, &c); --a; --b;
    g[a].push_back(b);
    g[b].push_back(a);

    gt[a].push_back(P(b, c));
    gt[b].push_back(P(a, c));
  }
  int m;
  scanf("%d", &m);
  rep(i, m) {
    scanf("%lld %lld", vs+i, ls+i); --vs[i];
    vv[vs[i]].push_back(i);
  }
  solve();
  rep(i, m) {
    printf("%lld\n", res[i]);
  }
  return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:315:18: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &n);
                  ^
./Main.cpp:317:47: 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;
                                               ^
./Main.cpp:325:18: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &m);
                  ^
./Main.cpp:327:35: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld %lld", vs+i, ls+i); --vs[i];
                                   ^

Judge Result