记录编号	160094	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[ZJOI 2015] 幻想乡战略游戏	最终得分	100
用户昵称	Asm.Def	是否通过	通过
代码语言	C++	运行时间	53.954 s
提交时间	2015-04-23 20:28:41	内存使用	36.40 MiB

/***********************************************************************/
/**********************By Asm.Def-Wu Jiaxin*****************************/
/***********************************************************************/
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <ctime>
#include <cctype>
#include <algorithm>
using namespace std;
#define SetFile(x) ( freopen(#x".in", "r", stdin), freopen(#x".out", "w", stdout) );
#define UseFREAD
#ifdef UseFREAD
#define getc() *(file_ptr++)
#define FreadLenth 5000000
char CHARPOOL[FreadLenth], *file_ptr = CHARPOOL;
#else
#define getc() getchar() 
#endif
#ifdef DEBUG
#include <sys/timeb.h>
timeb SysTp;
#endif
template<class T>inline void getd(T &x){
	char ch = getc();bool neg = false;
	while(!isdigit(ch) && ch != '-')ch = getc();
	if(ch == '-')ch = getc(), neg = true;
	x = ch - '0';
	while(isdigit(ch = getc()))x = x * 10 - '0' + ch;
	if(neg)x = -x;
}
/***********************************************************************/
const int maxn = 100005;
typedef long long LL;

int N, Q, lg2[maxn << 1], dfs_iter;

struct Node{
	Node *adj[22], *p, *Brid;
	int w[22], adj_d, dep, dis, id;//用于距离查询
	int size;//临时变量
	LL Val, Sum, Cont, Ans;//树分治
	int AnsTag;
	bool tag;
	inline void Link(Node *t, int v){
		w[adj_d] = v;
		adj[adj_d++] = t;
	}
	void dfs();void dfs2();
	Node *dp(int, int &);
	LL Query();
	inline void GetAns();
}T[maxn], *ST[18][maxn<<1], *Root;

void Node::dfs(){
	(*ST)[id = dfs_iter++] = this;
	int i;Node *to;
	for(i = 0;i < adj_d;++i)if((to = adj[i]) != p){
		to->p = this, to->dep = dep + 1, to->dis = dis + w[i];
		to->dfs();
		(*ST)[dfs_iter++] = this;
	}
}

inline Node * Cmp(Node *a, Node *b){return a->dep > b->dep ? b : a;}

inline void Build_ST(){
	int i = 2, j = 1, t = 4;
	while(i <= dfs_iter){
		if(i == t)++j, t <<= 1;
		lg2[i++] = j;
	}
	for(i = 1, t = 2;t <= dfs_iter;++i, t <<= 1)for(j = 0;j + t <= dfs_iter;++j)
		ST[i][j] = Cmp(ST[i-1][j], ST[i-1][j+(t >> 1)]);
}

inline int dist(Node *a, Node *b){
	int u = a->id, v = b->id;if(v < u)swap(u, v);
	int len = v - u + 1, lg = lg2[len];
	return a->dis + b->dis - (Cmp(ST[lg][u], ST[lg][v+1-(1 << lg)])->dis << 1);
}

void Node::dfs2(){
	size = 1;
	int i;Node *to;
	for(i = 0;i < adj_d;++i)if(!(to = adj[i])->tag && to != p){
		to->p = this;
		to->dfs2();
		size += to->size;
	}
}

Node * Node::dp(int psize, int &Maxsize){
	Node *ans = this, *to, *t;Maxsize = psize;
	int mx, i;
	for(i = 0;i < adj_d;++i)if((!(to = adj[i])->tag) && to != p)
		Maxsize = max(Maxsize, to->size);
	psize += size;
	for(i = 0;i < adj_d;++i)if((!(to = adj[i])->tag) && to != p){
		t = to->dp(psize - to->size, mx);
		if(mx < Maxsize)ans = t, Maxsize = mx;
	}
	return ans;
}

Node *Build_DC(Node *t){
	int s;t->p = NULL;
	t->dfs2();
	Node *root = t->dp(0, s), *to;
	root->tag = true;root->Brid = t;
	for(int i = 0;i < root->adj_d;++i){
		if((to = root->adj[i])->tag)swap(root->adj[i--], root->adj[--root->adj_d]);
		else{
			root->adj[i] = Build_DC(to);
			root->adj[i]->p = root;
		}
	}
	return root;
}

inline void Modify(Node *v, int d){
	v->Sum += d;
	Node *t = v;
	LL cont;
	while(t != Root){
		LL &s_cont = t->Cont;
		t = t->p;
		t->Sum += d;
		cont = (LL)dist(v, t) * d;
		t->Val += cont;s_cont += cont;
	}
}

inline void Node::GetAns(){
	if(AnsTag == Q)return;
	Ans = Val;
	Node *t = p;
	LL sum_d = Sum, cont = Cont, diff, dsum;
	while(t){
		diff = t->Val - cont;dsum = t->Sum - sum_d;
		if(dsum)Ans += diff + dsum * dist(t, this);
		sum_d = t->Sum, cont = t->Cont;
		t = t->p;
	}
	AnsTag = Q;
}

LL Node::Query(){
	GetAns();
	int i;Node *to;
	for(i = 0;i < adj_d;++i){
		(to = adj[i])->Brid->GetAns();
		if(to->Brid->Ans < Ans)return to->Query();
	}
	return Ans;
}

inline void init(){
	int i, a, b, c;
	for(i = 1;i < N;++i){
		getd(a), getd(b), getd(c);
		T[a].Link(T + b, c);
		T[b].Link(T + a, c);
	}
	T[1].dfs();
	Build_ST();
	(Root = Build_DC(T + 1))->p = 0x0;
}

int main(){

#ifdef DEBUG
	freopen("test.txt", "r", stdin);ftime(&SysTp);
	size_t Begin_sec = SysTp.time, Begin_mill = SysTp.millitm;
#elif !defined ONLINE_JUDGE
	SetFile(zjoi15_tree);
#endif
#ifdef UseFREAD
	fread(file_ptr, 1, FreadLenth, stdin);
#endif

	int u, e;
	getd(N), getd(Q);

	init();

	while(Q){
		getd(u), getd(e);
		Modify(T + u, e);
		printf("%lld\n", Root->Query());
		--Q;
	}

#ifdef DEBUG
	ftime(&SysTp);
	printf("\n%.3lf sec \n", (SysTp.time - Begin_sec) + (SysTp.millitm - Begin_mill) / 1000.0);
#endif
	return 0;
}