結果
| 問題 | No.1038 TreeAddQuery |
| ユーザー |
 heno239
|
| 提出日時 | 2020-08-02 14:00:39 |
| 言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 1,010 ms / 4,000 ms |
| コード長 | 7,724 bytes |
| コンパイル時間 | 1,854 ms |
| コンパイル使用メモリ | 146,368 KB |
| 実行使用メモリ | 74,588 KB |
| 最終ジャッジ日時 | 2024-07-18 12:34:39 |
| 合計ジャッジ時間 | 16,073 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 24 |
コンパイルメッセージ
In member function 'll Centroid_Decomposition::query(int, int, ll)',
inlined from 'void solve()' at main.cpp:372:20:
main.cpp:347:51: warning: 'id' may be used uninitialized [-Wmaybe-uninitialized]
347 | res -= dists[g][id].sum1(dec);
| ^
main.cpp: In function 'void solve()':
main.cpp:337:21: note: 'id' was declared here
337 | int id;
| ^~
In constructor 'BIT::BIT(BIT&&)',
inlined from 'void std::__new_allocator<_Tp>::construct(_Up*, _Args&& ...) [with _Up = BIT; _Args = {BIT}; _Tp = BIT]' at /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/bits/new_allocator.h:175:4,
inlined from 'static void std::allocator_traits<std::allocator<_CharT> >::construct(allocator_type&, _Up*, _Args&& ...) [with _Up = BIT; _Args = {BIT}; _Tp = BIT]' at /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/bits/alloc_traits.h:516:17,
inlined from 'void std::vector<_Tp, _Alloc>::emplace_back(_Args&& ...) [with _Args = {BIT}; _Tp = BIT; _Alloc = std::allocator<BIT>]' at /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/bits/vector.tcc:117:30,
inlined from 'void std::vector<_Tp, _Alloc>::push_back(value_type&&) [with _Tp = BIT; _Alloc = std::allocator<BIT>]' at /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/bits/stl_vector.h:1294:21,
inlined from 'Centroid_Decomposition::complete(int)::<lambda(std::vector<int>)>' at main.cpp:282:23:
main.cpp:184:8: warning: '<unnamed>.BIT::n' may be used uninitialized [-Wmaybe-uninitialized]
184 | struct BIT {
| ^~~
main.cpp: In lambda function:
main.cpp:282:51: note: '<anonymous>' declared here
282 | dists[g].push_back({});
| ~~~~~~~~~~~~~~~~~~^~~~
ソースコード
#include<iostream>#include<string>#include<cstdio>#include<vector>#include<cmath>#include<algorithm>#include<functional>#include<iomanip>#include<queue>#include<ciso646>#include<random>#include<map>#include<set>#include<bitset>#include<stack>#include<unordered_map>#include<utility>#include<cassert>#include<complex>#include<numeric>using namespace std;//#define int long longtypedef long long ll;typedef unsigned long long ul;typedef unsigned int ui;constexpr ll mod = 1000000007;const ll INF = mod * mod;typedef pair<int, int>P;#define stop char nyaa;cin>>nyaa;#define rep(i,n) for(int i=0;i<n;i++)#define per(i,n) for(int i=n-1;i>=0;i--)#define Rep(i,sta,n) for(int i=sta;i<n;i++)#define rep1(i,n) for(int i=1;i<=n;i++)#define per1(i,n) for(int i=n;i>=1;i--)#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)#define all(v) (v).begin(),(v).end()typedef pair<ll, ll> LP;typedef long double ld;typedef pair<ld, ld> LDP;const ld eps = 1e-12;const ld pi = acos(-1.0);ll mod_pow(ll x, ll n, ll m) {ll res = 1;while (n) {if (n & 1)res = res * x % m;x = x * x % m; n >>= 1;}return res;}struct modint {ll n;modint() :n(0) { ; }modint(ll m) :n(m) {if (n >= mod)n %= mod;else if (n < 0)n = (n % mod + mod) % mod;}operator int() { return n; }};bool operator==(modint a, modint b) { return a.n == b.n; }modint operator+=(modint& a, modint b) { a.n += b.n; if (a.n >= mod)a.n -= mod; return a; }modint operator-=(modint& a, modint b) { a.n -= b.n; if (a.n < 0)a.n += mod; return a; }modint operator*=(modint& a, modint b) { a.n = ((ll)a.n * b.n) % mod; return a; }modint operator+(modint a, modint b) { return a += b; }modint operator-(modint a, modint b) { return a -= b; }modint operator*(modint a, modint b) { return a *= b; }modint operator^(modint a, int n) {if (n == 0)return modint(1);modint res = (a * a) ^ (n / 2);if (n % 2)res = res * a;return res;}ll inv(ll a, ll p) {return (a == 1 ? 1 : (1 - p * inv(p % a, a)) / a + p);}modint operator/(modint a, modint b) { return a * modint(inv(b, mod)); }const int max_n = 1 << 17;modint fact[max_n], factinv[max_n];void init_f() {fact[0] = modint(1);for (int i = 0; i < max_n - 1; i++) {fact[i + 1] = fact[i] * modint(i + 1);}factinv[max_n - 1] = modint(1) / fact[max_n - 1];for (int i = max_n - 2; i >= 0; i--) {factinv[i] = factinv[i + 1] * modint(i + 1);}}modint comb(int a, int b) {if (a < 0 || b < 0 || a < b)return 0;return fact[a] * factinv[b] * factinv[a - b];}struct lcagraph {private:int n;vector<vector<int>> G;vector<vector<int>> parent;vector<int> depth;int root;int tmp;public:lcagraph(int n_) {n = n_;G.resize(n);parent.resize(n);depth.resize(n);tmp = 0;int cop = n;while (cop) {tmp++; cop /= 2;}rep(i, n)parent[i].resize(tmp);root = 0;}lcagraph() {}void init(int n_) {n = n_;G.resize(n);parent.resize(n);depth.resize(n);tmp = 0;int cop = n;while (cop) {tmp++; cop /= 2;}rep(i, n)parent[i].resize(tmp);root = 0;}void add_edge(int a, int b) {G[a].push_back(b);G[b].push_back(a);}void dfs(int id, int fr, int d) {parent[id][0] = fr;depth[id] = d;rep(j, G[id].size()) {int to = G[id][j];if (to == fr)continue;dfs(to, id, d + 1);}}void complete(int r = 0) {root = r;dfs(root, -1, 0);rep(j, tmp - 1)rep(i, n) {if (parent[i][j] < 0)parent[i][j + 1] = -1;else parent[i][j + 1] = parent[parent[i][j]][j];}}int lca(int u, int v) {if (depth[u] > depth[v])swap(u, v);for (int k = 0; k < tmp; k++) {if ((depth[v] - depth[u]) >> k & 1) {v = parent[v][k];}}if (u == v)return u;for (int k = tmp - 1; k >= 0; k--) {if (parent[u][k] != parent[v][k]) {u = parent[u][k];v = parent[v][k];}}return parent[u][0];}int dep(int x) {return depth[x];}int dist(int x, int y) {int l = lca(x, y);return depth[x] + depth[y] - 2 * depth[l];}int find_par(int x, int d) {rep(i, tmp)if (d & (1 << i))x = parent[x][i];return x;}};struct BIT {private:vector<ll> node; int n;public:BIT() {};BIT(int n_) {n = n_; node.resize(n, 0);}void init(int n_) {n = n_; node.resize(n, 0);}//0-indexedvoid add(int a, ll w) {if (a >= n)a = n - 1;for (int i = a; i < n; i |= i + 1)node[i] += w;}//[0,a)ll sum(int a) {if (a > n)a = n;ll ret = 0;for (int i = a - 1; i >= 0; i = (i & (i + 1)) - 1)ret += node[i];return ret;}//[a,b)ll sum(int a, int b) {return sum(b) - sum(a);}ll sum1(int a) {return sum(n) - sum(a);}};struct edge {int to;};struct Centroid_Decomposition {private:int n;vector<vector<edge>> G;vector<vector<int>> fG; int root;vector<int> par,parid;vector<vector<BIT>> dists;vector<BIT> pdist;lcagraph lg;public:Centroid_Decomposition(int n_) {n = n_;G.resize(n);par.resize(n);parid.resize(n);fG.resize(n); root = -1;dists.resize(n);pdist.resize(n);}void add_edge(int a, int b) {G[a].push_back({ b });G[b].push_back({ a });}void complete(int sup) {vector<int> exi(n, 0);vector<int> ori(n); rep(i, n)ori[i] = i;int tmp = 0;function<int(int, int, int&, int&)> szdfs = [&](int id, int fr, int& g, int& sz)->int {int res = 1;int ma = 0;for (edge e : G[id]) {if (tmp != exi[e.to])continue;if (e.to == fr)continue;int nex = szdfs(e.to, id, g, sz);ma = max(ma, nex);res += nex;}if (ma <= sz / 2 && sz - res <= sz / 2)g = id;return res;};function<int(vector<int>)> cdfs = [&](vector<int> v)->int {tmp++;if (v.empty())return 0;for (int id : v) {exi[id]++;}int g;int sz = v.size();szdfs(v[0], -1, g, sz);int ma = 0;for (edge e : G[g]) {if (!exi[e.to])continue;if (exi[e.to] != tmp)continue;int tm = dists[g].size();dists[g].push_back({});queue<P> vs;vs.push({ e.to,g });int d = 0;vector<int> nex;while (!vs.empty()) {d++;int len = vs.size();rep(aa, len) {P p = vs.front(); vs.pop();int v = p.first, fr = p.second;nex.push_back(v);for (edge e : G[v]) {if (e.to == fr)continue;if (tmp != exi[e.to])continue;vs.push({ e.to,v });}}}dists[g][tm].init(d+1);ma = max(ma, d);int ng = cdfs(nex);fG[g].push_back(ng);par[ng] = g;parid[ng] = tm;}pdist[g].init(ma + 1);for (int id : v) {exi[id]++;}tmp--;return g;};root = cdfs(ori); par[root] = -1;//lcalg.init(n);rep(i, n) {for (edge e : G[i]) {if (i < e.to) {lg.add_edge(i, e.to);}}}lg.complete();}ll query(int c, int x,ll y) {ll res = 0;int g = c;int id;while (g >= 0) {if (g == c) {res += pdist[g].sum1(0);pdist[g].add(x, y);}else {int dec = lg.dist(g, c);res += pdist[g].sum1(dec);res -= dists[g][id].sum1(dec);if (x - dec >= 0) {pdist[g].add(x - dec, y);dists[g][id].add(x - dec, y);}}id = parid[g];g = par[g];}return res;}};void solve() {int n,q; cin >> n>>q;Centroid_Decomposition cd(n);rep(i, n-1) {int a, b; cin >> a >> b; a--; b--;cd.add_edge(a, b);}cd.complete(n);rep(i, q) {int x, y, z; cin >> x >> y >> z; x--;ll ans = cd.query(x, y, z);cout << ans << "\n";}}signed main() {ios::sync_with_stdio(false);cin.tie(0);//cout << fixed << setprecision(10);//init_f();//cout << grandy(2, 3, false, false) << "\n";//int t; cin >> t; rep(i, t)solve();return 0;}