/* このコード、と~おれ! Be accepted! ∧_∧  (。・ω・。)つ━☆・*。 ⊂   ノ    ・゜+.  しーJ   °。+ *´¨)          .· ´¸.·*´¨) ¸.·*¨)           (¸.·´ (¸.·'* ☆ */ #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include /*多倍長整数/cpp_intで宣言 #include using namespace boost::multiprecision; */ //#pragma gcc target ("avx2") //#pragma gcc optimization ("o3") //#pragma gcc optimization ("unroll-loops") #define rep(i, n) for(int i = 0; i < (n); ++i) #define rep1(i, n) for(int i = 1; i <= (n); ++i) #define rep2(i, n) for(int i = 2; i < (n); ++i) #define repr(i, n) for(int i = n; i >= 0; --i) #define reprm(i, n) for(int i = n - 1; i >= 0; --i) #define printynl(a) printf(a ? "yes\n" : "no\n") #define printyn(a) printf(a ? "Yes\n" : "No\n") #define printYN(a) printf(a ? "YES\n" : "NO\n") #define printim(a) printf(a ? "possible\n" : "imposible\n") #define printdb(a) printf("%.50lf\n", a) //少数出力 #define printLdb(a) printf("%.50Lf\n", a) //少数出力 #define printdbd(a) printf("%.16lf\n", a) //少数出力(桁少なめ) #define prints(s) printf("%s\n", s.c_str()) //string出力 #define all(x) (x).begin(), (x).end() #define allsum(a, b, c) ((a + b) * c / 2LL) //等差数列の和、初項,末項,項数 #define pb push_back #define rpriq priq, greater> #define deg_to_rad(deg) (((deg)/360.0L)*2.0L*PI) #define rad_to_deg(rad) (((rad)/2.0L/PI)*360.0L) #define Please return #define AC 0 #define manhattan_dist(a, b, c, d) (abs(a - c) + abs(b - d)) /*(a, b) から (c, d) のマンハッタン距離 */ using ll = long long; constexpr int INF = 1073741823; constexpr int MINF = -1073741823; constexpr ll LINF = ll(4661686018427387903); constexpr ll MOD = 1000000007; const long double PI = acosl(-1.0L); using namespace std; void scans(string& str) { char c; str = ""; scanf("%c", &c); if (c == '\n')scanf("%c", &c); while (c != '\n' && c != -1 && c != ' ') { str += c; scanf("%c", &c); } } void scanc(char& str) { char c; scanf("%c", &c); if (c == -1)return; while (c == '\n') { scanf("%c", &c); } str = c; } double acot(double x) { return PI / 2 - atan(x); } ll LSB(ll n) { return (n & (-n)); } /*-----------------------------------------ここからコード-----------------------------------------*/ //セグ木/0-indexed/非再帰/n の大きさ, a (単位元), 本体のマージ関数, 遅延ノードの単位元, 遅延ノードのマージ関数, 遅延ノードと本体のマージ関数 で segtree を初期化する template struct lazysegtree { //木を配列であらわしたもの vector seg; //遅延ノード vector lazy; //サイズノード vector size; //遅延ノードのフラグ管理 vector flag; //木の1/2の大きさ int siz, height; //本体の単位元 const T se; //遅延ノードの単位元 const U le; //本体のマージ関数の型 using F = function; //遅延ノードのマージ関数の型 using F2 = function; //遅延ノードと本体のマージ関数の型 using F3 = function; //サイズを使った演算をする関数の型 using F4 = function; //本体同士をマージする関数 const F f; //遅延ノード同士をマージする関数 const F2 f2; //遅延ノードと本体をマージする関数 const F3 f3; //サイズを使った演算をする関数 const F4 f4; //n の大きさ, a (単位元), 本体のマージ関数, 遅延ノードの単位元, 遅延ノードのマージ関数, 遅延ノードと本体のマージ関数, サイズを使った演算をする関数 で segtree を初期化する lazysegtree(int n, const T se, const F f, const U le, const F2 f2, const F3 f3, const F4 f4) : se(se), f(f), le(le), f2(f2), f3(f3), f4(f4) { siz = 1; height = 0; while (siz < n)siz <<= 1, ++height; seg.assign(2 * siz - 1, se); lazy.assign(2 * siz - 1, le); size.assign(2 * siz - 1, 1); flag.assign(2 * siz - 1, false); --siz; } //k (0-indexed) 番目に t を代入 void set(int k, const T& t) { seg[k + siz] = t; } //f によって木を構築 void build() { for (int i = siz - 1; i >= 0; --i) { seg[i] = f(seg[i * 2 + 1], seg[i * 2 + 2]); size[i] = size[i * 2 + 1] + size[i * 2 + 2]; } } //i 番目の要素を返す T operator[](const int i) { return query(i, i + 1); } //k 番目の遅延ノードを伝播する inline T merge(int k) { return (!flag[k] ? seg[k] : f3(seg[k], f4(lazy[k], size[k]))); } //子に伝播 inline void eval(int k) { if (flag[k]) { lazy[k * 2 + 1] = f2(lazy[k * 2 + 1], lazy[k]); lazy[k * 2 + 2] = f2(lazy[k * 2 + 2], lazy[k]); flag[k * 2 + 1] = flag[k * 2 + 2] = true; seg[k] = merge(k); lazy[k] = le; flag[k] = false; } } inline void bottomup(int k) { while (k > 0) { k = ((k - 1) >> 1); seg[k] = f(merge(2 * k + 1), merge(2 * k + 2)); } } inline void topdown(int k) { for (int i = height; i > 0; --i) { eval(((k + 1) >> i) - 1); } } //k 番目の値を a に更新 void update(int k, T a) { k += siz; //必要であればここを変える seg[k] = a; while (k > 0) { k = ((k - 1) >> 1); seg[k] = f(seg[k * 2 + 1], seg[k * 2 + 2]); } } //[l, r) の値を a に更新 void update(int l, int r, T a) { int x = l + siz, y = r + siz - 1; topdown(x); topdown(y); for (l += siz, r += siz; l < r; l >>= 1, r >>= 1) { if (!(l & 1)) { lazy[l] = f2(lazy[l], a); flag[l] = true; ++l; } if (!(r & 1)) { --r; lazy[r] = f2(lazy[r], a); flag[r] = true; } } bottomup(x); bottomup(y); } //[a, b) について f した結果を返す T query(int a, int b) { topdown(a += siz); topdown(b += siz - 1); T l = se, r = se; for (++b; a < b; a >>= 1, b >>= 1) { if (!(a & 1))l = f(l, merge(a++)); if (!(b & 1))r = f(merge(--b), r); } return f(l, r); } ////[start, end) について、[l, r) を調べながら k 番目が check を満たすか二分探索 最後が true なら left, false なら right fの逆演算 //template //int find(const int start, const int end, int l, int r, int k, const C check, T& checknum, const bool b, const function revf) { // //cerr << checknum << '\n'; // //範囲外またはそこがすでに満たさないとき // //cerr << k << ',' << checknum << '\n'; // if (start <= l && r <= end && !check(seg[k], checknum)) { // checknum = revf(checknum, seg[k]); // return -1; // } // if ((r <= start || l >= end)) { // return -1; // } // //既に葉 // if (k >= siz) { // return k - siz; // } // int res; // if (b) { // //左側を調べる // res = find< C >(start, end, l, ((l + r) >> 1), (k << 1) + 1, check, checknum, b, revf); // //左側が適してたらそれが答え // if (res != -1)return (res); // return find< C >(start, end, ((l + r) >> 1), r, (k << 1) + 2, check, checknum, b, revf); // } // else { // //右側を調べる // res = find< C >(start, end, ((l + r) >> 1), r, (k << 1) + 2, check, checknum, b, revf); // //右側が適してたらそれが答え // if (res != -1)return (res); // return find< C >(start, end, l, ((l + r) >> 1), (k << 1) + 1, check, checknum, b, revf); // } //} //template //int find_left(int start, int end, const C check, T checknum, function revf) { // return find< C >(start, end, 0, siz + 1, 0, check, checknum, true, revf); //} //template //int find_right(int start, int end, const C check, T checknum, function revf) { // return find< C >(start, end, 0, siz + 1, 0, check, checknum, false, revf); //} }; void dfs(const vector>& tree, vector& id, const int& now, const int& bef, const int& cnt) { id[now] = cnt; for (const auto& aa : tree[now]) { if (aa != bef)dfs(tree, id, aa, now, cnt + 1); } } int main() { int n, q; scanf("%d%d", &n, &q); vector> tree(n); int a, b; rep(i, n - 1) { scanf("%d%d", &a, &b); --a; --b; tree[a].push_back(b); tree[b].push_back(a); } int leaf = 0; rep(i, n) { if (tree[i].size() == 1) { leaf = i; break; } } vector id(n); dfs(tree, id, leaf, -1, 0); lazysegtree seg(114514, 0, plus(), 0, plus(), plus(), [](int a, int d) {return a * d; }); seg.build(); int x, y, z; rep(i, q) { scanf("%d%d%d", &x, &y, &z); --x; printf("%d\n", seg[id[x]]); int l = max(0, id[x] - y), r = min(114514, id[x] + y + 1); seg.update(l, r, z); } Please AC; }