結果
| 問題 | No.1637 Easy Tree Query |
| ユーザー |
 kusaf_
|
| 提出日時 | 2021-08-19 17:00:38 |
| 言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
AC
|
| 実行時間 | 246 ms / 2,000 ms |
| コード長 | 10,171 bytes |
| コンパイル時間 | 2,029 ms |
| コンパイル使用メモリ | 176,580 KB |
| 実行使用メモリ | 17,280 KB |
| 最終ジャッジ日時 | 2024-04-20 19:49:25 |
| 合計ジャッジ時間 | 10,123 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge3 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 5 ms
9,600 KB |
| testcase_01 | AC | 5 ms
9,600 KB |
| testcase_02 | AC | 246 ms
12,672 KB |
| testcase_03 | AC | 6 ms
9,472 KB |
| testcase_04 | AC | 59 ms
11,136 KB |
| testcase_05 | AC | 210 ms
10,696 KB |
| testcase_06 | AC | 140 ms
10,368 KB |
| testcase_07 | AC | 78 ms
9,532 KB |
| testcase_08 | AC | 51 ms
10,880 KB |
| testcase_09 | AC | 157 ms
11,904 KB |
| testcase_10 | AC | 98 ms
10,240 KB |
| testcase_11 | AC | 222 ms
12,244 KB |
| testcase_12 | AC | 215 ms
11,520 KB |
| testcase_13 | AC | 37 ms
10,220 KB |
| testcase_14 | AC | 94 ms
11,904 KB |
| testcase_15 | AC | 198 ms
12,288 KB |
| testcase_16 | AC | 141 ms
12,672 KB |
| testcase_17 | AC | 62 ms
10,300 KB |
| testcase_18 | AC | 190 ms
10,640 KB |
| testcase_19 | AC | 188 ms
10,880 KB |
| testcase_20 | AC | 233 ms
11,648 KB |
| testcase_21 | AC | 116 ms
11,120 KB |
| testcase_22 | AC | 227 ms
12,660 KB |
| testcase_23 | AC | 60 ms
10,320 KB |
| testcase_24 | AC | 89 ms
11,256 KB |
| testcase_25 | AC | 211 ms
10,640 KB |
| testcase_26 | AC | 232 ms
11,648 KB |
| testcase_27 | AC | 242 ms
12,544 KB |
| testcase_28 | AC | 146 ms
10,496 KB |
| testcase_29 | AC | 183 ms
11,520 KB |
| testcase_30 | AC | 55 ms
11,476 KB |
| testcase_31 | AC | 163 ms
9,472 KB |
| testcase_32 | AC | 90 ms
10,624 KB |
| testcase_33 | AC | 203 ms
10,260 KB |
| testcase_34 | AC | 69 ms
17,280 KB |
ソースコード
#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);
}
}