結果

問題 No.1637 Easy Tree Query
ユーザー kusaf_
提出日時 2021-08-19 17:00:38
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 275 ms / 2,000 ms
コード長 10,171 bytes
コンパイル時間 2,017 ms
コンパイル使用メモリ 179,068 KB
実行使用メモリ 17,280 KB
最終ジャッジ日時 2024-10-12 17:44:21
合計ジャッジ時間 11,568 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 33
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <bits/stdc++.h>
using namespace std;
// Basic
#define ll int64_t
const ll INF=(1LL<<60);
#define p_ii pair<ll,ll>
#define p_dd pair<double,double>
#define p_is pair<ll,string>
#define p_si pair<string,ll>
#define m_ii(v) map<ll,ll> v;
#define m_si(v) map<string,ll> v;
#define fi first
#define sc second
#define mp make_pair
struct UnionFind {
  /*
    unite(x,y) : x と y の木を併合
    same(x,y) : x と y の属する木が同じなら true
  */
    vector<int> par; // par[i] : iの親の番号
    vector<int> usiz; // usiz[i] : iを含む連結成分のサイズ
    UnionFind(int n) : par(n),usiz(n) {
        for(int i = 0; i < n; i++){
             par[i] = i;
             usiz[i] = 1;
        }
    }
    int root(int x) {
        if (par[x] == x) return x;
        return par[x] = root(par[x]);
    }
    void unite(int x, int y) {
        int rx = root(x);
        int ry = root(y);
        if (rx == ry) return;
        if (usiz[rx] > usiz[ry]){
          par[ry] = rx;
          usiz[rx] += usiz[ry];
        } else {
          par[rx] = ry;
          usiz[ry] += usiz[rx];
        }
        //par[rx] = ry;
    }
    bool same(int x, int y) {
        int rx = root(x);
        int ry = root(y);
        return rx == ry;
    }
    int siz(int x){ return usiz[root(x)];}
};
struct RMQ {
  /*
    set(ll i, ll x), build(): i番目の要素をxにセット。まとめてセグ木を構築する。O(n)
    update(i,x): i 番目の要素を x に更新。O(log(n))
    query(a,b): [a,b) での最小の要素を取得。O(log(n))
    find_rightest(a,b,x): [a,b) で x以下の要素を持つ最右位置を求める。O(log(n))
    find_leftest(a,b,x): [a,b) で x以下の要素を持つ最左位置を求める。O(log(n))
  */
    const ll e = numeric_limits<ll>::max();
    function<ll(ll, ll)> fx = [](ll x1, ll x2) -> ll { return min(x1, x2); };
    ll n;
    vector<ll> dat;
    RMQ(ll n_) : n(), dat(n_ * 4, e) {
        ll x = 1;
        while (n_ > x) {
            x *= 2;
        }
        n = x;
    }
    void set(ll i, ll x) { dat[i + n - 1] = x; }
    void build() {
        for (ll k = n - 2; k >= 0; k--) dat[k] = fx(dat[2 * k + 1], dat[2 * k + 2]);
    }
    void update(ll i, ll x) {
        i += n - 1;
        dat[i] = x;
        while (i > 0) {
            i = (i - 1) / 2;
            dat[i] = fx(dat[i * 2 + 1], dat[i * 2 + 2]);
        }
    }
    // the minimum element of [a,b)
    ll query(ll a, ll b) { return query_sub(a, b, 0, 0, n); }
    ll query_sub(ll a, ll b, ll k, ll l, ll r) {
        if (r <= a || b <= l) {
            return e;
        } else if (a <= l && r <= b) {
            return dat[k];
        } else {
            ll vl = query_sub(a, b, k * 2 + 1, l, (l + r) / 2);
            ll vr = query_sub(a, b, k * 2 + 2, (l + r) / 2, r);
            return fx(vl, vr);
        }
    }
    ll find_rightest(ll a, ll b, ll x) { return find_rightest_sub(a, b, x, 0, 0, n); }
    ll find_leftest(ll a, ll b, ll x) { return find_leftest_sub(a, b, x, 0, 0, n); }
    ll find_rightest_sub(ll a, ll b, ll x, ll k, ll l, ll r) {
        if (dat[k] > x || r <= a || b <= l) {  // 自分の値がxより大きい or [a,b)が[l,r)の範囲外ならreturn a-1
            return a - 1;
        } else if (k >= n - 1) {  // 自分が葉ならその位置をreturn
            return (k - (n - 1));
        } else {
            ll vr = find_rightest_sub(a, b, x, 2 * k + 2, (l + r) / 2, r);
            if (vr != a - 1) {  // 右の部分木を見て a-1 以外ならreturn
                return vr;
            } else {  // 左の部分木を見て値をreturn
                return find_rightest_sub(a, b, x, 2 * k + 1, l, (l + r) / 2);
            }
        }
    }
    ll find_leftest_sub(ll a, ll b, ll x, ll k, ll l, ll r) {
        if (dat[k] > x || r <= a || b <= l) {  // 自分の値がxより大きい or [a,b)が[l,r)の範囲外ならreturn b
            return b;
        } else if (k >= n - 1) {  // 自分が葉ならその位置をreturn
            return (k - (n - 1));
        } else {
            ll vl = find_leftest_sub(a, b, x, 2 * k + 1, l, (l + r) / 2);
            if (vl != b) {  // 左の部分木を見て b 以外ならreturn
                return vl;
            } else {  // 右の部分木を見て値をreturn
                return find_leftest_sub(a, b, x, 2 * k + 2, (l + r) / 2, r);
            }
        }
    }
};
// Loop
#define lp(i,n) for(ll i=0;i<n;i++)
#define lp_(i,n) for(ll i=0;i<=n;i++)    // 条件に＝つき
#define lpp(i,n,m) for(ll i=n;i<m;i++)
#define lpp_(i,n,m) for(ll i=n;i<=m;i++)
// vector定義
#define _GLIBCXX_DEBUG
#define vec(v,n) vector<int> v(n)       // int
#define vec_(v,n,m) vector<int> v(n,m)  // int 初期条件あり
#define vec64(v,n) vector<ll> v(n)      // int64_t
#define vec64_(v,n,m) vector<ll> v(n,m) // int64_t 初期条件あり
#define vecd(v,n) vector<double> v(n)   // double
#define vecc(v,n) vector<char> v(n)     // char
#define vecs(v,n) vector<string> v(n)   // string
#define vece(v) vector<ll> v;           // int 空
#define vecec(v) vector<char> v;        // char 空
#define vecp(v,n) vector<p_ii> v(n)     // pair
#define vec2i(v,h,w) vector<vector<ll>> v(h,vector<ll>(w))    // 二次元配列 int
#define vec2c(v,h,w) vector<vector<char>> v(h,vector<char>(w))  // 二次元配列 char
// vector,string操作
#define vin(v) \
{\
  lp(i,v.size())\
    cin>>v[i];\
}                              // 入力
#define vini(v,n) \
{\
  lp(i,v.size())\
  {\
    lp(j,v.at(0).size())\
      v[i][j]=n;\
  }\
}                           // 二次元配列初期化
#define all(v) v.begin(),v.end()
#define si(v) int(v.size())                      // サイズ
#define back(v) v.back()                         // 最後の要素
#define sum(v) accumulate(all(v),0)              // 総和
#define sort(v) sort(all(v))                     // ソート
#define reverse(v) reverse(all(v))               // 反転
#define lower(v,x) lower_bound(all(v),x)-v.begin() // a[i]<xとなるiの個数
#define upper(v,x) upper_bound(all(v),x)-v.begin() // a[i]<=xとなるiの個数
#define cou(v,n) count(all(v),n)                 // n の出現回数を数える
#define pb(v,n) v.push_back(n)                   // 最後尾に n を追加
#define ins(v,i,n) v.insert(v.begin()+i,n)       // 場所を指定してv[i]に n を追加
#define del(v) v.pop_back()                      // 最後尾を削除
#define del0(v) v.erase(v.begin())               // 最初の要素v[0]を削除
#define del_(v,i) v.erase(v.begin()+i)           // 場所を指定してv[i]を削除
#define del__(v,i,j) v.erase(v.begin()+i,v.begin()+j+1)  // 範囲を指定してv[i]~v[j]を削除
#define sub(s,i,j) s.substr(i,j-i+1)             // 範囲を指定してs[i]~s[j]を取得【stringのみ】
// functions
const ll MOD=1000000007;
const int COMAX = 510000;
ll COMdp[100][100],fac[COMAX], finv[COMAX], inv[COMAX];
int wa(ll x){
  int sum=0;
  for(;x!=0;)
  {
    sum+=x%10;
    x/=10;
  }
  return sum;
}                  // 各位の和
int keta(ll x){
  int r=0;
  while(x!=0)
  {
    x/=10;
    r++;
  }
  return r;
}                // 桁数
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < COMAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}
ll COM_M(ll n, ll k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;}          // nCk（MODで割った余り）← 適宜COMAX変更!!
ll COM(ll n, ll k){
    if(n==k) return COMdp[n][k] = 1;
    if(k==0) return COMdp[n][k] = 1;
    if(k==1) return COMdp[n][k] = n;
    if(COMdp[n][k]) return COMdp[n][k];
    return COMdp[n][k] = COM(n-1,k) + COM(n-1,k-1);}            // nCk（答えが2^64まで，余りは出さない）← 適宜COMdp変更!!
ll pow_M(ll a, ll n){
    ll res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % MOD;
        a = a * a % MOD;
        n >>= 1;
    }
    return res;}          // a^n（MODで割った余り）
vector<ll> n_sin(ll x,ll n){
  vector<ll> r;
  while(x!=0)
  {
    pb(r,x%n);
    x=x-x%n;
    x/=n;
  }
  reverse(r);
  return r;}   // n進法
ll kiri(ll a,ll b){
  ll r=(a+b-1)/b;
  return r;
}            // 割り算（小数点以下切り上げ）
ll kai_M(ll n){
  ll r=1;
  lpp_(i,2,n)
  {
    r*=i;
    r%=MOD;
  }
  return r;}                // n!（MODで割った余り）
vector<ll> prime_p(ll x){
    vector<ll> pri;
    for(ll d=2;d*d<=x;d++)
    {
      if(x%d!=0)
        continue;
      ll ex=0;
      while(x%d==0)
      {
        ex++;
        x/=d;
      }
      pb(pri,ex);
    }
    if(x!=1)
      pb(pri,1);
    return pri;
  }      // 素因数分解（～乗の部分のみ）
vector<ll> prime_a(ll x){
    vector<ll> res;
    for (ll a=2;a*a<=x;a++)
    {
      if (x%a!=0) continue;
      while (x%a==0)
        x/= a;
      pb(res,a);
    }
    if (x != 1) pb(res,x);
    return res;
  }      // 素因数分解（素因数を返すだけ）
vector<p_ii> prime(ll x){
    vector<pair<ll, ll>> res;
    for (ll a=2;a*a<=x;a++)
    {
      if (x%a!=0) continue;
      ll ex=0;
      while (x%a==0)
      {
        ++ex;
        x /= a;
      }
      res.push_back({a, ex});
    }
    if (x != 1) res.push_back({x, 1});
    return res;}      // 素因数分解（…の～乗<pair>）
// others
#define under(n) cout<<fixed<<setprecision(n) // 小数点以下の桁数を指定
#define cout(n) cout<<n<<endl
#define en cout<<endl
#define Y cout("Yes")                         // "Yes"
#define N cout("No")                          // "No"
using Graph = vector<vector<int>>;
using wGraph = vector<vector<p_ii>>;
Graph g(200010);
vec64_(f,200010,1);
void dfs(ll v,ll p)
{
  for(auto nv:g[v]) if(nv!=p) dfs(nv,v);
  for(auto nv:g[v]) if(nv!=p) f[v]+=f[nv];
}
int main()
{
  ll n,q,r=0; cin>>n>>q;
  lp(i,n-1)
  {
    ll a,b; cin>>a>>b;
    a--; b--;
    pb(g[a],b);
    pb(g[b],a);
  }
  dfs(0,-1);
  lp(i,q)
  {
    ll a,b; cin>>a>>b;
    a--;
    r+=f[a]*b;
    cout(r);
  }
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0