记录编号	235090	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[ZJOI 2015] 幻想乡战略游戏	最终得分	100
用户昵称	stdafx.h	是否通过	通过
代码语言	C++	运行时间	32.910 s
提交时间	2016-03-10 10:38:18	内存使用	16.32 MiB

#define maxn 100010ul

#define ll long long

#include <stdio.h>
#include <algorithm>

struct Edge{ll v,w,nx;};
struct Edge_none_w{ll v,nx;};
const ll inf=1ll<<62ll;

namespace tree_div{
	Edge *edge;
	ll *headlist,top[maxn],size[maxn],son[maxn],fa[maxn],dis[maxn],depth[maxn];
	ll lca(ll x,ll y){
		while(top[x]!=top[y]){
			if(depth[top[x]]>depth[top[y]]) x=fa[top[x]];
			else y=fa[top[y]];
		}
		return depth[x]<depth[y]?x:y;
	}
	ll dist(ll x,ll y){
		return dis[x]+dis[y]-(dis[lca(x,y)]<<1);
	}
	void dfs1(ll p){
		size[p]=1;
		for(ll i=headlist[p];i;i=edge[i].nx){
			if(fa[p]==edge[i].v) continue;
			dis[edge[i].v]=dis[p]+edge[i].w;
			depth[edge[i].v]=depth[p]+1;
			fa[edge[i].v]=p,dfs1(edge[i].v);
			size[p]+=size[edge[i].v];
			if(!son[p]||size[edge[i].v]>size[son[p]]) son[p]=edge[i].v;
		}
		return;
	}
	void dfs2(ll p,ll tp){
		top[p]=tp;
		if(son[p]) dfs2(son[p],tp);
		for(ll i=headlist[p];i;i=edge[i].nx){
			if(edge[i].v==son[p]||edge[i].v==fa[p]) continue;
			dfs2(edge[i].v,edge[i].v);
		}
		return;
	}
	void build(Edge *e,ll *h){
		edge=e,headlist=h;
		depth[1]=1,dfs1(1),dfs2(1,1);
		return;
	}
}

Edge edge[maxn<<1],e2[maxn];
ll n,q,ec,ec2,h2[maxn],headlist[maxn],dfa[maxn],fs[maxn],gr;ll mark[maxn],exp_mark[maxn],etr[maxn];
bool ex[maxn];

ll Min(ll a,ll b){
	return a<b?a:b;
}

void Add_Edge2(ll u,ll v,ll w){
	e2[++ec2].v=v;
	e2[ec2].w=w;
	e2[ec2].nx=h2[u];
	h2[u]=ec2;
	return;
}

void Add_Edge(ll u,ll v,ll w){
	edge[++ec].v=v;
	edge[ec].w=w;
	edge[ec].nx=headlist[u];
	headlist[u]=ec;
	return;
}

ll tree_size(ll p,ll fa){
	ll size_=1;
	for(ll i=headlist[p];i;i=edge[i].nx){
		if(ex[edge[i].v]||edge[i].v==fa) continue;
		size_+=tree_size(edge[i].v,p);
	}
	return size_;
}

ll gravity(ll p,ll fa,ll tot,ll &center){
	ll size_=1,k;bool flag=true;
	for(ll i=headlist[p];i;i=edge[i].nx){
		if(ex[edge[i].v]||edge[i].v==fa) continue;
		k=gravity(edge[i].v,p,tot,center);
		if((k<<1)>tot) flag=false;
		size_+=k;
	}
	if((tot-size_<<1)>tot) flag=false;
	if(flag) center=p;
	return size_;
}

ll divide(ll p){
	ll center,center_of_son,min_dis;
	gravity(p,0,tree_size(p,0),center),ex[center]=true,fs[center]=p;
	for(ll i=headlist[center];i;i=edge[i].nx) if(!ex[edge[i].v]){
		center_of_son=divide(edge[i].v);
		dfa[center_of_son]=center,Add_Edge2(center,center_of_son,edge[i].w);
	}
	return center;
}

ll cal(ll x){
	if(!x) return inf;
	ll ans=etr[x];ll cur_dis,last=0;
	for(ll i=x;i;last=i,i=dfa[i]){
		cur_dis=tree_div::dist(x,i);
		ans+=exp_mark[last];
		ans+=cur_dis*mark[last];
	}
	return ans;
}

ll query(ll p){
	ll ans=cal(p),k;
	for(ll i=h2[p];i;i=e2[i].nx){
		k=cal(fs[e2[i].v]);
		if(k<ans) return query(e2[i].v);
	}
	return ans;
}

ll work(ll x,ll add){
	ll can_not_choose=0;ll ans=inf,am;
	for(ll i=x;i;can_not_choose=i,i=dfa[i]){
		am=tree_div::dist(x,i)*add,etr[i]+=am;
		for(ll k=h2[i];k;k=e2[k].nx){
			if(e2[k].v==can_not_choose) continue;
			mark[e2[k].v]+=add,exp_mark[e2[k].v]+=am;
		}
	}
	return query(gr);
}

int main(){
    int __size__=168<<20;
	char *__p__=(char*)malloc(__size__)+__size__;
	__asm__("movl %0, %%esp\n"::"r"(__p__));
	freopen("zjoi15_tree.in","r",stdin);
	freopen("zjoi15_tree.out","w",stdout);
	scanf("%lld%lld",&n,&q);
	for(ll i=1,a,b,t;i<n;i++){
		scanf("%lld%lld%lld",&a,&b,&t);
		Add_Edge(a,b,t),Add_Edge(b,a,t);
	}
	tree_div::build(edge,headlist);
	divide(1);
	for(ll i=1;i<=n;i++) if(!dfa[i]) gr=i;
	for(ll i=0,x,t;i<q;i++){
		scanf("%lld%lld",&x,&t);
		printf("%lld\n",work(x,t));
	}
	return 0;
}