結果
| 問題 | No.1038 TreeAddQuery |
| コンテスト | |
| ユーザー |
 chocorusk
|
| 提出日時 | 2020-05-01 05:08:20 |
| 言語 | C++17 (gcc 15.2.0 + boost 1.89.0) |
| 結果 |
AC
|
| 実行時間 | 1,918 ms / 4,000 ms |
| コード長 | 5,309 bytes |
| 記録 | |
| コンパイル時間 | 1,866 ms |
| コンパイル使用メモリ | 150,100 KB |
| 最終ジャッジ日時 | 2025-01-10 03:54:21 |
|
ジャッジサーバーID （参考情報） |
judge3 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 24 |
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:198:32: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
198 | int a, b; scanf("%d %d", &a, &b); a--; b--;
| ~~~~~^~~~~~~~~~~~~~~~~
main.cpp:221:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
221 | scanf("%d %d %lld", &x, &y, &z);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
ソースコード
#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_popcount
using namespace std;
typedef long long int ll;
typedef pair<int, int> P;
const int MAXN=100010;
vector<vector<int>> g;
int sz[MAXN], par[MAXN];
bool isremoved[MAXN];
vector<int> centroids;
int dist[MAXN];
void findcentroid_rec(int x, int p, int size, vector<P> &v){
sz[x]=1, par[x]=p;
v.push_back({x, dist[x]});
bool cent=1;
for(auto y:g[x]){
if(y==p) continue;
if(isremoved[y]) continue;
dist[y]=dist[x]+1;
findcentroid_rec(y, x, size, v);
if(sz[y]>size/2) cent=0;
sz[x]+=sz[y];
}
if(size-sz[x]>size/2) cent=0;
if(cent) centroids.push_back(x);
}
pair<int, vector<pair<int, int>>> findcentroid(int root, int size, vector<P> &v){
vector<pair<int, int>> subtrees;
centroids.clear();
findcentroid_rec(root, -1, size, v);
int cent=centroids[0];
for(auto y:g[cent]){
if(isremoved[y]) continue;
if(y==par[cent]){
subtrees.push_back({y, size-sz[cent]});
}else{
subtrees.push_back({y, sz[y]});
}
}
return make_pair(cent, subtrees);
}
int parc[MAXN];
vector<P> vd[MAXN], vdc[MAXN];
void dfs(int x, int p, int cent){
vd[cent].push_back({x, dist[x]});
for(auto y:g[x]){
if(y==p) continue;
if(isremoved[y]) continue;
dist[y]=dist[x]+1;
dfs(y, x, cent);
}
}
void myon(int root, int size, int p=-1){
if(size<=1){
parc[root]=p;
vdc[root].push_back({root, 0});
vd[root].push_back({root, 0});
return;
}
dist[root]=0;
vector<P> v;
auto pr=findcentroid(root, size, v);
int cent=pr.first;
swap(vdc[cent], v);
dist[cent]=0;
dfs(cent, -1, cent);
parc[cent]=p;
isremoved[cent]=1;
for(auto prr:pr.second){
if(!isremoved[prr.first]){
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;
g.resize(n);
for(int i=0; i<n-1; i++){
int a, b; scanf("%d %d", &a, &b); a--; b--;
g[a].push_back(b);
g[b].push_back(a);
}
myon(0, n);
int mx[MAXN]={}, mxc[MAXN]={};
for(int i=0; i<n; i++){
sort(vd[i].begin(), vd[i].end());
for(auto x:vd[i]) mx[i]=max(mx[i], x.second+1);
}
vector<RangeAddPointGet<ll>> seg(n), segc(n);
for(int i=0; i<n; i++){
seg[i].init(mx[i]);
}
for(int i=0; i<n; i++){
sort(vdc[i].begin(), vdc[i].end());
for(auto x:vdc[i]) mxc[i]=max(mxc[i], x.second+1);
segc[i].init(mxc[i]);
}
LCA lca(g);
lca.build();
while(q--){
int x, y; ll z;
scanf("%d %d %lld", &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);
d1=y-lca.dist(x, x1);
if(d1<0) d1=-1;
seg[x1].add(0, min(d1+1, mx[x1]), z);
if(parc[x1]!=-1){
t=lower_bound(vdc[x1].begin(), vdc[x1].end(), P(x, 0))-vdc[x1].begin();
d1=vdc[x1][t].second;
ans+=segc[x1].get(d1);
d1=y-lca.dist(x, parc[x1])-1;
if(d1<0) d1=-1;
segc[x1].add(0, min(d1+1, mxc[x1]), -z);
}
x1=parc[x1];
}
printf("%lld\n", ans);
}
return 0;
}