結果
| 問題 | No.1038 TreeAddQuery |
| ユーザー |
 chocorusk
|
| 提出日時 | 2020-04-25 00:02:55 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
TLE
(最新)
AC
(最初)
|
| 実行時間 | - |
| コード長 | 6,815 bytes |
| コンパイル時間 | 2,951 ms |
| コンパイル使用メモリ | 158,100 KB |
| 最終ジャッジ日時 | 2025-01-10 00:42:57 |
|
ジャッジサーバーID （参考情報） |
judge3 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 14 TLE * 10 |
ソースコード
#include <cstdio>#include <cstring>#include <iostream>#include <string>#include <cmath>#include <bitset>#include <vector>#include <map>#include <set>#include <queue>#include <deque>#include <algorithm>#include <complex>#include <unordered_map>#include <unordered_set>#include <random>#include <cassert>#include <fstream>#include <utility>#include <functional>#include <time.h>#include <stack>#include <array>#define popcount __builtin_popcountusing namespace std;typedef long long int ll;typedef pair<int, int> P;const int MAX_V = 100010; // ツリーのサイズのありうる最大値int N; // ツリーのサイズvector<vector<int>> tree; // ツリーを隣接リスト形式のグラフ構造で表したものint sizeSubtree[MAX_V]; // sizeSubtree[v] := v を根とする部分ツリーのサイズ (分割統治の毎ステップごとに再利用)bool isRemoved[MAX_V]; // isRemoved[v] := v が既に取り除かれたかどうかint whoIsParent[MAX_V]; // whoIsParent[v] := ツリーDP時に v の親が誰だったか// メイン処理vector<int> centroids;void FindCentroidRecursive(int v, int size, int p = -1) {sizeSubtree[v] = 1;whoIsParent[v] = p;bool isCentroid = true;for (auto ch : tree[v]) {if (ch == p) continue;if (isRemoved[ch]) continue;FindCentroidRecursive(ch, size, v);if (sizeSubtree[ch] > size / 2) isCentroid = false;sizeSubtree[v] += sizeSubtree[ch];}if (size - sizeSubtree[v] > size / 2) isCentroid = false;if (isCentroid) centroids.push_back(v);}// 初期化void Init() {for (int i = 0; i < MAX_V; ++i) {isRemoved[i] = false;}}// first: 重心, second: (重心の子ノード, 子部分木のサイズ) からなるベクトルpair<int, vector<pair<int,int> > > FindCentroid(int root, int size) {vector<pair<int, int> > subtrees;centroids.clear();FindCentroidRecursive(root, size);int center = centroids[0];for (auto ch : tree[center]) {if (isRemoved[ch]) continue;if (ch == whoIsParent[center]) {subtrees.push_back(make_pair(ch, size - sizeSubtree[center]));}else {subtrees.push_back(make_pair(ch, sizeSubtree[ch]));}}return make_pair(center, subtrees);}int par[100010];vector<P> vd[100010];int dist[100010];void dfs(int v, int p, int cent){whoIsParent[v] = p;vd[cent].push_back({v, dist[v]});for(auto ch:tree[v]){if (ch == p) continue;if (isRemoved[ch]) continue;dist[ch]=dist[v]+1;dfs(ch, v, cent);}}map<P, int> ind;int id;vector<vector<P>> vdc;int pc[100010];void dfs1(int v, int p, int cent){vdc[cent].push_back({v, dist[v]});for(auto ch:tree[v]){if (ch == p) continue;if (isRemoved[ch]) continue;dist[ch]=dist[v]+1;dfs1(ch, v, cent);}}void myon(int root, int size, int p=-1){if(size<=1){par[root]=p;if(p!=-1) pc[root]=root;else pc[root]=-1;vd[root].push_back({root, 0});return;}auto pr=FindCentroid(root, size);int cent=pr.first;if(p!=-1) pc[cent]=root;else pc[cent]=-1;dist[cent]=0;dfs(cent, -1, cent);par[cent]=p;isRemoved[cent]=1;for(auto prr:pr.second){if(!isRemoved[prr.first]){dist[prr.first]=0;ind[{cent, prr.first}]=id;vector<P> nw;vdc.push_back(nw);dfs1(prr.first, -1, id);id++;myon(prr.first, prr.second, cent);}}}struct LCA{vector<vector<int>> g;vector<int> d;vector<vector<int>> p;int log;int n;LCA(const vector<vector<int>> &g):g(g), d(g.size()), n(g.size()){log=0;while(1<<log<=n) log++;p.resize(log, vector<int>(n));}void dfs(int x, int prev){for(auto y:g[x]){if(y==prev) continue;d[y]=d[x]+1;p[0][y]=x;dfs(y, x);}}void build(){dfs(0, -1);for(int i=1; i<log; i++){for(int j=0; j<n; j++){p[i][j]=p[i-1][p[i-1][j]];}}}int lca(int a, int b){if(d[a]>d[b]) swap(a, b);int dd=d[b]-d[a], i=0;int a1=a, b1=b;while(dd){if(dd&1) b1=p[i][b1];dd>>=1;i++;}if(a1==b1) return a1;for(int j=log-1; j>=0; j--){if(p[j][a1]!=p[j][b1]){a1=p[j][a1], b1=p[j][b1];}}return p[0][a1];}int dist(int a, int b){return d[a]+d[b]-2*d[lca(a, b)];}};template<typename T>struct BIT{vector<T> bit;int size;BIT(){}BIT(int n):size(n), bit(n+1, 0){}void init(int n){size=n; bit.resize(n+1);}T sum(int i){ //[0, i)T s=0;while(i>0){s+=bit[i];i-=(i&(-i));}return s;}T sum(int l, int r){ //[l, r)return sum(r)-sum(l);}void add(int i, T x){i++;while(i<=size){bit[i]+=x;i+=(i&(-i));}}};template<typename T>struct RangeAddPointGet{BIT<T> bit;RangeAddPointGet(){}RangeAddPointGet(int n):bit(n){}void init(int n){bit.init(n);}void add(int l, int r, T x){bit.add(l, x);bit.add(r, -x);}T get(int i){return bit.sum(i+1);}};int main(){int n, q; cin>>n>>q;tree.resize(n);for(int i=0; i<n-1; i++){int a, b; cin>>a>>b; a--; b--;tree[a].push_back(b);tree[b].push_back(a);}myon(0, n);for(int i=0; i<n; i++){sort(vd[i].begin(), vd[i].end());}for(int i=0; i<id; i++) sort(vd[i].begin(), vd[i].end());vector<RangeAddPointGet<ll>> seg(n), segc(id);for(int i=0; i<n; i++){seg[i].init(vd[i].size());}for(int i=0; i<id; i++){sort(vdc[i].begin(), vdc[i].end());segc[i].init(vdc[i].size());}LCA lca(tree);lca.build();while(q--){int x, y; ll z;cin>>x>>y>>z;x--;int x1=x;ll ans=0;while(x1!=-1){int t=lower_bound(vd[x1].begin(), vd[x1].end(), P(x, 0))-vd[x1].begin();int d1=vd[x1][t].second;ans+=seg[x1].get(d1);int p=pc[x1];x1=par[x1];if(x1!=-1){p=ind[{x1, p}];t=lower_bound(vdc[p].begin(), vdc[p].end(), P(x, 0))-vdc[p].begin();d1=vdc[p][t].second;ans+=segc[p].get(d1);}}printf("%lld\n", ans);x1=x;while(x1!=-1){int d1=y-lca.dist(x, x1);if(d1<0) d1=-1;if(d1>=(int)vd[x1].size()) d1=(int)vd[x1].size()-1;seg[x1].add(0, d1+1, z);int p=pc[x1];x1=par[x1];if(x1!=-1){p=ind[{x1, p}];d1=y-lca.dist(x, x1)-1;if(d1<0) d1=-1;if(d1>=(int)vdc[p].size()) d1=(int)vdc[p].size()-1;segc[p].add(0, d1+1, -z);}}}return 0;}