This documentation is automatically generated by online-judge-tools/verification-helper
// verification-helper: PROBLEM http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0367
#include <bits/stdc++.h>
using namespace std;
#define call_from_test
#include "../../tools/fixpoint.cpp"
#include "../../tools/trio.cpp"
#include "../../tree/heavylightdecomposition.cpp"
#include "../../segtree/basic/ushi.cpp"
#undef call_from_test
signed main(){
cin.tie(0);
ios::sync_with_stdio(0);
using ll = long long;
int n,k;
cin>>n>>k;
HLD hld(n);
using P = pair<int, int>;
map<P, int> es;
for(int i=1;i<n;i++){
int a,b,c;
cin>>a>>b>>c;
hld.add_edge(a,b);
es[P(a,b)]=es[P(b,a)]=c;
}
hld.build();
vector<ll> dep(n);
MFP([&](auto dfs,int v,int p,ll d)->void{
dep[v]=d;
for(int u:hld.G[v])
if(u!=p) dfs(u,v,d+es[P(u,v)]);
})(0,-1,0);
vector<ll> ws(n,0);
auto con=[&](int a,int b){return hld.par[a]==b||hld.par[b]==a;};
auto cst=
[&](int a,int b)->ll{
if(!con(a,b)) return 0;
ll res=ws[a]+ws[b]+abs(dep[a]-dep[b]);
return res%k?res:0;
};
using T = trio<int, int, ll>;
T ti(-1,-1,-1);
auto f=
[&](T a,T b){
if(a.first<0||a.second<0) return b;
if(b.first<0||b.second<0) return a;
for(int i=0;i<2;i++){
for(int j=0;j<2;j++){
if(con(a.first,b.first))
return T(a.second,b.second,a.third+b.third+cst(a.first,b.first));
swap(a.first,a.second);
}
swap(b.first,b.second);
}
return ti;
};
SegmentTree<T> seg(f,ti);
vector<T> vt;
for(int i=0;i<n;i++)
vt.emplace_back(hld.inv[i],hld.inv[i],0);
seg.build(vt);
int q;
cin>>q;
for(int i=0;i<q;i++){
string op;
cin>>op;
if(op=="add"){
int x,d;
cin>>x>>d;
ws[x]+=d;
seg.set_val(hld.vid[x],T(x,x,0));
}
if(op=="send"){
int s,t;
cin>>s>>t;
int u=hld.lca(s,t);
T r1(ti),r2(ti);
hld.for_each(s,u,[&](int l,int r){r1=f(r1,seg.query(l,r));});
hld.for_each_edge(t,u,[&](int l,int r){r2=f(r2,seg.query(l,r));});
cout<<f(r1,r2).third<<"\n";
}
}
cout<<flush;
return 0;
}
#line 1 "test/aoj/0367.test.cpp"
// verification-helper: PROBLEM http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0367
#include <bits/stdc++.h>
using namespace std;
#define call_from_test
#line 1 "tools/fixpoint.cpp"
#line 3 "tools/fixpoint.cpp"
using namespace std;
#endif
//BEGIN CUT HERE
template<typename F>
struct FixPoint : F{
FixPoint(F&& f):F(forward<F>(f)){}
template<typename... Args>
decltype(auto) operator()(Args&&... args) const{
return F::operator()(*this,forward<Args>(args)...);
}
};
template<typename F>
inline decltype(auto) MFP(F&& f){
return FixPoint<F>{forward<F>(f)};
}
//END CUT HERE
#ifndef call_from_test
//INSERT ABOVE HERE
signed main(){
return 0;
}
#endif
#line 1 "tools/trio.cpp"
#line 3 "tools/trio.cpp"
using namespace std;
#endif
//BEGIN CUT HERE
template<typename T, typename U, typename V>
struct trio{
T first;
U second;
V third;
trio(T first,U second,V third):
first(first),second(second),third(third){}
operator tuple<T&, U&, V&>(){
return forward_as_tuple(first,second,third);
}
using X = tuple<T, U, V>;
operator X() const{return make_tuple(first,second,third);}
bool operator==(const trio&a) const{return (X)(*this)==(X)a;}
bool operator!=(const trio&a) const{return (X)(*this)!=(X)a;}
bool operator< (const trio&a) const{return (X)(*this)< (X)a;}
bool operator<=(const trio&a) const{return (X)(*this)<=(X)a;}
bool operator> (const trio&a) const{return (X)(*this)> (X)a;}
bool operator>=(const trio&a) const{return (X)(*this)>=(X)a;}
};
template<typename T, typename U, typename V>
trio<T, U, V> make_trio(T first,U second,V third){
return trio<T, U, V>(first,second,third);
}
//END CUT HERE
#ifndef call_from_test
signed main(){
return 0;
}
#endif
#line 1 "tree/heavylightdecomposition.cpp"
#line 3 "tree/heavylightdecomposition.cpp"
using namespace std;
#endif
//BEGIN CUT HERE
class HLD{
private:
void dfs_sz(int v) {
auto &es=G[v];
if(~par[v]) es.erase(find(es.begin(),es.end(),par[v]));
for(int &u:es){
par[u]=v;
dfs_sz(u);
sub[v]+=sub[u];
if(sub[u]>sub[es[0]]) swap(u,es[0]);
}
}
void dfs_hld(int v,int &pos) {
vid[v]=pos++;
inv[vid[v]]=v;
for(int u:G[v]){
if(u==par[v]) continue;
nxt[u]=(u==G[v][0]?nxt[v]:u);
dfs_hld(u,pos);
}
}
public:
vector< vector<int> > G;
// vid: vertex -> idx
// inv: idx -> vertex
vector<int> vid,nxt,sub,par,inv;
HLD(int n):G(n),vid(n,-1),nxt(n),sub(n,1),par(n,-1),inv(n){}
void add_edge(int u,int v) {
G[u].emplace_back(v);
G[v].emplace_back(u);
}
void build(int r=0) {
int pos=0;
dfs_sz(r);
nxt[r]=r;
dfs_hld(r,pos);
}
int lca(int u,int v){
while(1){
if(vid[u]>vid[v]) swap(u,v);
if(nxt[u]==nxt[v]) return u;
v=par[nxt[v]];
}
}
template<typename F>
void for_each(int u,int v,const F& f) {
while(1){
if(vid[u]>vid[v]) swap(u,v);
f(max(vid[nxt[v]],vid[u]),vid[v]+1);
if(nxt[u]!=nxt[v]) v=par[nxt[v]];
else break;
}
}
template<typename F>
void for_each_edge(int u,int v,const F& f) {
while(1){
if(vid[u]>vid[v]) swap(u,v);
if(nxt[u]!=nxt[v]){
f(vid[nxt[v]],vid[v]+1);
v=par[nxt[v]];
}else{
if(u!=v) f(vid[u]+1,vid[v]+1);
break;
}
}
}
};
//END CUT HERE
#ifndef call_from_test
signed main(){
return 0;
};
#endif
#line 1 "segtree/basic/ushi.cpp"
#line 3 "segtree/basic/ushi.cpp"
using namespace std;
#endif
//BEGIN CUT HERE
template <typename T>
struct SegmentTree{
using F = function<T(T,T)>;
int n;
F f;
T ti;
vector<T> dat;
SegmentTree(F f,T ti):f(f),ti(ti){}
void init(int n_){
n=1;
while(n<n_) n<<=1;
dat.assign(n<<1,ti);
}
void build(const vector<T> &v){
int n_=v.size();
init(n_);
for(int i=0;i<n_;i++) dat[n+i]=v[i];
for(int i=n-1;i;i--)
dat[i]=f(dat[(i<<1)|0],dat[(i<<1)|1]);
}
void set_val(int k,T x){
dat[k+=n]=x;
while(k>>=1)
dat[k]=f(dat[(k<<1)|0],dat[(k<<1)|1]);
}
T query(int a,int b){
if(a>=b) return ti;
T vl=ti,vr=ti;
for(int l=a+n,r=b+n;l<r;l>>=1,r>>=1) {
if(l&1) vl=f(vl,dat[l++]);
if(r&1) vr=f(dat[--r],vr);
}
return f(vl,vr);
}
template<typename C>
int max_right(int s,C &check,T &acc,int k,int l,int r){
if(l+1==r){
acc=f(acc,dat[k]);
return check(acc)?-1:k-n;
}
int m=(l+r)>>1;
if(m<=s) return max_right(s,check,acc,(k<<1)|1,m,r);
if(s<=l and check(f(acc,dat[k]))){
acc=f(acc,dat[k]);
return -1;
}
int vl=max_right(s,check,acc,(k<<1)|0,l,m);
if(~vl) return vl;
return max_right(s,check,acc,(k<<1)|1,m,r);
}
// max t s.t. check(query(s,t))
// O(\log N)
template<typename C>
int max_right(int s,C &check){
assert(s<n and check(ti) and not check(query(s,n)));
T acc=ti;
return max_right(s,check,acc,1,0,n);
}
};
//END CUT HERE
#ifndef call_from_test
signed main(){
return 0;
}
#endif
#line 11 "test/aoj/0367.test.cpp"
#undef call_from_test
signed main(){
cin.tie(0);
ios::sync_with_stdio(0);
using ll = long long;
int n,k;
cin>>n>>k;
HLD hld(n);
using P = pair<int, int>;
map<P, int> es;
for(int i=1;i<n;i++){
int a,b,c;
cin>>a>>b>>c;
hld.add_edge(a,b);
es[P(a,b)]=es[P(b,a)]=c;
}
hld.build();
vector<ll> dep(n);
MFP([&](auto dfs,int v,int p,ll d)->void{
dep[v]=d;
for(int u:hld.G[v])
if(u!=p) dfs(u,v,d+es[P(u,v)]);
})(0,-1,0);
vector<ll> ws(n,0);
auto con=[&](int a,int b){return hld.par[a]==b||hld.par[b]==a;};
auto cst=
[&](int a,int b)->ll{
if(!con(a,b)) return 0;
ll res=ws[a]+ws[b]+abs(dep[a]-dep[b]);
return res%k?res:0;
};
using T = trio<int, int, ll>;
T ti(-1,-1,-1);
auto f=
[&](T a,T b){
if(a.first<0||a.second<0) return b;
if(b.first<0||b.second<0) return a;
for(int i=0;i<2;i++){
for(int j=0;j<2;j++){
if(con(a.first,b.first))
return T(a.second,b.second,a.third+b.third+cst(a.first,b.first));
swap(a.first,a.second);
}
swap(b.first,b.second);
}
return ti;
};
SegmentTree<T> seg(f,ti);
vector<T> vt;
for(int i=0;i<n;i++)
vt.emplace_back(hld.inv[i],hld.inv[i],0);
seg.build(vt);
int q;
cin>>q;
for(int i=0;i<q;i++){
string op;
cin>>op;
if(op=="add"){
int x,d;
cin>>x>>d;
ws[x]+=d;
seg.set_val(hld.vid[x],T(x,x,0));
}
if(op=="send"){
int s,t;
cin>>s>>t;
int u=hld.lca(s,t);
T r1(ti),r2(ti);
hld.for_each(s,u,[&](int l,int r){r1=f(r1,seg.query(l,r));});
hld.for_each_edge(t,u,[&](int l,int r){r2=f(r2,seg.query(l,r));});
cout<<f(r1,r2).third<<"\n";
}
}
cout<<flush;
return 0;
}