結果
| 問題 | No.1038 TreeAddQuery |
| ユーザー |
 leaf_1415
|
| 提出日時 | 2020-04-24 23:40:07 |
| 言語 | C++11 (gcc 13.3.0) |
| 結果 |
AC
|
| 実行時間 | 913 ms / 4,000 ms |
| コード長 | 4,447 bytes |
| コンパイル時間 | 1,032 ms |
| コンパイル使用メモリ | 89,468 KB |
| 実行使用メモリ | 57,372 KB |
| 最終ジャッジ日時 | 2024-11-25 04:44:57 |
| 合計ジャッジ時間 | 13,550 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 24 |
ソースコード
#include <iostream>#include <cstdio>#include <cmath>#include <ctime>#include <cstdlib>#include <cassert>#include <vector>#include <list>#include <stack>#include <queue>#include <deque>#include <map>#include <set>#include <bitset>#include <string>#include <algorithm>#include <utility>#define llint long long#define inf 1e18#define rep(x, s, t) for(llint (x) = (s); (x) < (t); (x)++)#define Rep(x, s, t) for(llint (x) = (s); (x) <= (t); (x)++)#define chmin(x, y) (x) = min((x), (y))#define chmax(x, y) (x) = max((x), (y))#define mod 1000000007using namespace std;typedef pair<llint, llint> P;struct BIT{int size;vector<llint> bit;BIT(){size = 0;}BIT(int s){size = s;bit.resize(size+1);init();}void init(){for(int i = 1; i <= size; i++) bit[i] = 0;}llint query(int i){llint ret = 0;while(i > 0){ret += bit[i];i -= i&(-i);}return ret;}void add(int i, llint x){while(i <= size){bit[i] += x;i += i&(-i);}}};llint n, Q;vector<llint> G[100005];llint x[100005], y[100005], z[100005];vector<llint> qvec[100005];llint size[200005], depth[200005];bool used[200005];llint ans[200005];BIT bit(100005);int sizedfs(int v, int pre){int ret = 1;for(int i = 0; i < G[v].size(); i++){if(G[v][i] == pre) continue;if(used[G[v][i]]) continue;ret += sizedfs(G[v][i], v);}return size[v] = ret;}int centdfs(int v, int pre, int sz){for(int i = 0; i < G[v].size(); i++){if(G[v][i] == pre) continue;if(used[G[v][i]]) continue;if(size[G[v][i]] > sz/2) return centdfs(G[v][i], v, sz);}return v;}vector<P> vec;vector<llint> vvec[100005], gvvec[100005];void finddfs(int v, int p, int d){depth[v] = d;vvec[d].push_back(v);for(int i = 0; i < qvec[v].size(); i++) vec.push_back(P(depth[v], qvec[v][i]));for(int i = 0; i < G[v].size(); i++){if(G[v][i] == p) continue;if(used[G[v][i]]) continue;finddfs(G[v][i], v, d+1);}}void calc(vector<llint> vvec[], vector<P> vec[], vector<P> vec2[], llint dep){for(int i = 0; i <= dep; i++){for(int j = 0; j < vec[i].size(); j++){//cout << "+ " << vec[i][j].first << " " << vec[i][j].second << endl;bit.add(vec[i][j].first, vec[i][j].second);}for(int j = 0; j < vvec[i].size(); j++){llint v = vvec[i][j];//cout << i << " " << v << endl;for(int k = 0; k < qvec[v].size(); k++){ans[qvec[v][k]] += bit.query(qvec[v][k]-1);}}for(int j = 0; j < vec2[i].size(); j++){//cout << "- " << vec2[i][j].first << " " << vec2[i][j].second << endl;bit.add(vec2[i][j].first, vec2[i][j].second);}}}vector<P> global[100005], global2[100005];vector<P> local[100005], local2[100005];void solve(int v){sizedfs(v, -1);v = centdfs(v, -1, size[v]);sizedfs(v, -1);//cout << v << endl;/* 処理 */for(int i = 0; i <= size[v]; i++){global[i].clear(), global2[i].clear();gvvec[i].clear();}for(int i = 0; i < G[v].size(); i++){if(used[G[v][i]]) continue;vec.clear();for(int j = 0; j <= size[G[v][i]]; j++){local[j].clear(), local2[j].clear();vvec[j].clear();}finddfs(G[v][i], v, 1);for(int j = 0; j < vec.size(); j++){llint qid = vec[j].second;if(vec[j].first > y[qid]) continue;llint dep = min(size[v], y[qid]-vec[j].first);global[0].push_back(P(qid, z[qid]));global2[dep].push_back(P(qid, -z[qid]));if(dep >= 1){dep = min(dep, size[G[v][i]]);local[1].push_back(P(qid, -z[qid]));local2[dep].push_back(P(qid, z[qid]));}}calc(vvec, local, local2, size[G[v][i]]);for(int j = 0; j <= size[G[v][i]]; j++){for(int k = 0; k < vvec[j].size(); k++){gvvec[j].push_back(vvec[j][k]);}}}gvvec[0].push_back(v);for(int i = 0; i < qvec[v].size(); i++){llint qid = qvec[v][i], dep = min(size[v], y[qid]);global[0].push_back(P(qid, z[qid]));global2[dep].push_back(P(qid, -z[qid]));}calc(gvvec, global, global2, size[v]);used[v] = true;for(int i = 0; i < G[v].size(); i++){if(used[G[v][i]]) continue;solve(G[v][i]);}}int main(void){ios::sync_with_stdio(0);cin.tie(0);cin >> n >> Q;llint u, v;for(int i = 1; i <= n-1; i++){cin >> u >> v;G[u].push_back(v);G[v].push_back(u);}for(int i = 1; i <= Q; i++){cin >> x[i] >> y[i] >> z[i];qvec[x[i]].push_back(i);}solve(1);for(int i = 1; i <= Q; i++) cout << ans[i] << "\n";flush(cout);return 0;}