记录编号	477891	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[ZJOI 2015] 幻想乡战略游戏	最终得分	100
用户昵称	LadyLex	是否通过	通过
代码语言	C++	运行时间	15.316 s
提交时间	2017-12-07 19:20:17	内存使用	24.83 MiB

#include <cstdio>
#include <cstring>
using namespace std;
#define LL long long
#define N 100010
#define LL long long
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
struct edge{int zhong,next,val;};
struct G
{
	edge s[N<<1];int e,adj[N];
	G(){e=0;memset(adj,0,sizeof(adj));}
	inline void add(int qi,int zhong,int val=0)
		{s[++e].zhong=zhong;s[e].next=adj[qi];adj[qi]=e;s[e].val=val;}
}T1,T2;
int n,q,f[N<<1][18],logn[N<<1],bin[25],tp;
LL s[3][N],sum,ans,len[N];
int dfn[N],num;
inline void dfs1(int rt,int fa)
{
	f[(dfn[rt]=++num)][0]=len[rt];
	for(int i=T1.adj[rt];i;i=T1.s[i].next)
		if(T1.s[i].zhong!=fa)
			len[T1.s[i].zhong]=len[rt]+T1.s[i].val,dfs1(T1.s[i].zhong,rt),f[++num][0]=len[rt];
}
inline LL LCA(int a,int b)
{
	if(dfn[a]>dfn[b])a^=b,b^=a,a^=b;
	int k=logn[dfn[b]-dfn[a]+1];
	return min(f[dfn[a]][k],f[dfn[b]-bin[k]+1][k])<<1;
}
inline LL dis(int a,int b){return len[a]+len[b]-LCA(a,b);}
int size[N],maxs[N],totsize,root,Vater[N];
bool vis[N];
inline void dfs2(int rt,int fa)
{
	size[rt]=1,maxs[rt]=0;
	for(int i=T1.adj[rt];i;i=T1.s[i].next)
		if(!vis[T1.s[i].zhong]&&T1.s[i].zhong!=fa)
			dfs2(T1.s[i].zhong,rt),size[rt]+=size[T1.s[i].zhong],
			maxs[rt]=max(size[T1.s[i].zhong],maxs[rt]);
	maxs[rt]=max(totsize-size[rt],maxs[rt]);
	if(maxs[rt]<maxs[root])root=rt;
}
inline void dfs3(int rt,int fa)
{
	Vater[rt]=fa;vis[rt]=1;int siz=totsize;
	for(int i=T1.adj[rt];i;i=T1.s[i].next)
		if(!vis[T1.s[i].zhong])
		{
			if(size[T1.s[i].zhong]>size[rt])totsize=siz-size[rt];
			else totsize=size[T1.s[i].zhong];
			root=0,dfs2(T1.s[i].zhong,0),T2.add(rt,root,T1.s[i].zhong),dfs3(root,rt);
		}
}
inline void update(int who,LL val)
{
	for(int rt=who;rt;rt=Vater[rt])
	{
		s[0][rt]+=val,s[1][rt]+=dis(rt,who)*val;
		if(Vater[rt])s[2][rt]+=dis(Vater[rt],who)*val;
	}
}
inline LL calc(int rt)
{
	LL ret=0;
	for(int x=rt;x;x=Vater[x])
	{
		ret+=s[1][x];
		if(Vater[x])ret+=-s[2][x]+(s[0][Vater[x]]-s[0][x])*dis(Vater[x],rt);
	}
	return ret;
}
inline LL getans(int rt)
{
	LL temp=calc(rt);
	for(int i=T2.adj[rt];i;i=T2.s[i].next)
		if(calc(T2.s[i].val)<temp)return getans(T2.s[i].zhong);//*******
	return temp;
}
char B[1<<15],*S=B,*T=B;
#define getc ( S==T&&(T=(S=B)+fread(B,1,1<<15,stdin),S==T)?0:*S++)
inline int read()
{
	int x=0,f=1;register char c=getc;
	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getc;}
	while(c>='0'&&c<='9')x=10*x+(c^48),c=getc;
	return x*f;
}
int main()
{
	freopen("zjoi15_tree.in","r",stdin);
	freopen("zjoi15_tree.out","w",stdout);
	// freopen("Ark.in","r",stdin);
	register int i,j,orig,a,b,c;
	n=read();q=read();
	for(bin[0]=i=1;i<=20;++i)bin[i]=bin[i-1]<<1;
	while(bin[tp+1]<=(n<<1))++tp;
	for(logn[0]=-1,i=1;i<=(n<<1);++i)logn[i]=logn[i>>1]+1;
	for(i=1;i<n;++i)
		a=read(),b=read(),c=read(),T1.add(a,b,c),T1.add(b,a,c);
	dfs1(1,0),root=0,maxs[0]=n+1,totsize=n,dfs2(1,0);
	for(i=1;i<=tp;++i)
		for(j=1;j+bin[i]-1<=(n<<1);++j)
			f[j][i]=min(f[j][i-1],f[j+bin[i-1]][i-1]);
	orig=root,dfs3(root,0);
	while(q--)
		a=read(),b=read(),update(a,b),printf("%lld\n",getans(orig));
}