#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define popcount __builtin_popcount using namespace std; typedef long long int ll; typedef pair P; const int MAX_V = 100010; // ツリーのサイズのありうる最大値 int N; // ツリーのサイズ vector> tree; // ツリーを隣接リスト形式のグラフ構造で表したもの int sizeSubtree[MAX_V]; // sizeSubtree[v] := v を根とする部分ツリーのサイズ (分割統治の毎ステップごとに再利用) bool isRemoved[MAX_V]; // isRemoved[v] := v が既に取り除かれたかどうか int whoIsParent[MAX_V]; // whoIsParent[v] := ツリーDP時に v の親が誰だったか // メイン処理 vector 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 > > FindCentroid(int root, int size) { vector > 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

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 ind; int id; vector> 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

nw; vdc.push_back(nw); dfs1(prr.first, -1, id); id++; myon(prr.first, prr.second, cent); } } } struct LCA{ vector> g; vector d; vector> p; int log; int n; LCA(const vector> &g):g(g), d(g.size()), n(g.size()){ log=0; while(1<(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; id[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 struct BIT{ vector 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 struct RangeAddPointGet{ BIT 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>a>>b; a--; b--; tree[a].push_back(b); tree[b].push_back(a); } myon(0, n); for(int i=0; i> seg(n), segc(id); for(int i=0; i>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; }