davidwang's Blog

第一次写维护点分治的树

然后因为大错一个数字调了半个小时是在蛋疼，最近开的坑太多赶脚没有时间填了

算了一点点来吧

//coder : davidwang
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <climits>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <bitset>
#include <deque>
#include <iostream>
using namespace std;
#define LL long long
#define X first
#define Y second
template<typename T>
inline T sqr(const T &x){ return x*x; }
inline int read()
{
	int ret=0,f=1; char ch;
	for (ch=getchar();ch<'0' || ch>'9';ch=getchar())
		if (ch=='-') f=-f;
	for (;'0'<=ch && ch<='9';ch=getchar())
		ret=ret*10+ch-'0';
	return ret*f;
}
const int N = 12010;
int start[N],to[N<<1],next[N<<1],len[N<<1],cnt,size[N],q[N],d[N];
int vis[N],use[N],fa[N],Pre[N],col[N],fl[N],inf=INT_MAX,p[N][20],pl[N][20];
int n,m,T;
multiset<pair<int,int> >S[N];
multiset<int>ans;
multiset<pair<int,int> >::iterator it,i1,i2;
inline void connect(int x,int y,int l){
	to[++cnt]=y; next[cnt]=start[x]; start[x]=cnt; len[cnt]=l;
}
inline int bfs(int x,int flag=0)
{
	vis[x]=1;
	int head=0,tail=1,u,v;
	q[1]=x; vis[x]=1;
	while (head<tail){
		u=q[++head];
		for (int p=start[u];p;p=next[p]){
			if (!vis[to[p]]&&!use[to[p]]){
				q[++tail]=to[p];
				fa[to[p]]=u;
				vis[to[p]]=1;
				if (flag==2){
					d[to[p]]=d[u]+1;
					fl[to[p]]=len[p];
				}
			}
		}
	}
	for (int i=1;i<=tail;i++) vis[q[i]]=0;
	if (flag==0||flag==2){
		return tail;
	}
	for (int i=1;i<=tail;i++){
		int x=q[i];
		size[x]=0;
	}
	int Max=tail+1,cur=0,y=-1;
	for (int i=tail;i;i--){
		int x=q[i];
		size[x]++; size[fa[x]]+=size[x];
		cur=0;
		for (int p=start[x];p;p=next[p])
			if (to[p]!=fa[x] && vis[to[p]]){
				cur=max(cur,size[to[p]]);
			}
			
		cur=max(cur,tail-size[x]);
		if (cur<Max){
			Max=cur;
			y=x;
		}
	}
	return y;
}
inline int lca(int x,int y){
	if (d[x]<d[y]) swap(x,y);
	int ans=0,j;
	while (d[x]>d[y]){
		for (j=1;d[p[x][j]]>=d[y];j++);
		ans+=pl[x][j-1]; x=p[x][j-1];
	}
	while (x!=y){
		for (j=1;p[x][j]!=p[y][j];j++);
		ans+=pl[x][j-1]+pl[y][j-1];
		x=p[x][j-1],y=p[y][j-1];
	}
	return ans;
}
void dfs(int x,int f){
	x=bfs(x,1);
	int n=bfs(x,0);
	use[x]=1; Pre[x]=f;
	for (int i=1;i<=n;i++)
		S[x].insert(make_pair(col[q[i]],lca(q[i],x)));
	int nowC=0,tot=0,flag=0;
	for (it=S[x].begin();it!=S[x].end();it++){
		if (it->X!=nowC){
			nowC=it->X;
			tot=0; flag=0;
		}
		if (it->X==nowC){
			tot++;
			if (tot<=2) flag+=it->Y;
			if (tot==2) ans.insert(flag);
		}
	}
	for (int p=start[x];p;p=next[p])
		if (!use[to[p]]) dfs(to[p],x);
}
inline int Make_Ans(multiset<pair<int,int> >& S,int c){
	i1=i2=S.upper_bound(make_pair(c,-1));
	if (i1==S.end() || i1->X!=c) return inf;
	i2++;
	if (i2==S.end() || i2->X!=c) return inf;
	int ret=i1->Y+i2->Y;
	return ret;
}
void modify(int x,int y,int c1,int c2){
	if (x==0) return;
	int d=lca(x,y);
	set<int>::iterator now=ans.find(Make_Ans(S[x],c1));
	if (now!=ans.end()) ans.erase(now);
	S[x].erase(S[x].find(make_pair(c1,d)));
	ans.insert(Make_Ans(S[x],c1));
	
	now=ans.find(Make_Ans(S[x],c2));
	if (now!=ans.end()) ans.erase(now);
	S[x].insert(make_pair(c2,d));
	ans.insert(Make_Ans(S[x],c2));
	
	modify(Pre[x],y,c1,c2);
}
int init()
{
#ifndef ONLINE_JUDGE
	freopen("a.in","r",stdin);
	freopen("a.out","w",stdout);
#endif
	n=read();
	for (int i=1;i<=n;i++) col[i]=read();
	for (int i=1;i<n;i++){
		int x=read(),y=read(),z=read();
		connect(x,y,z);
		connect(y,x,z);
	}
	bfs(1,2); d[0]=-1;
	for (int i=1;i<=10;i++) ans.insert(inf); 
	for (int i=1;i<=n;i++) p[i][0]=fa[i],pl[i][0]=fl[i];
	for (int j=1;j<20;j++)
		for (int i=1;i<=n;i++)
			p[i][j]=p[p[i][j-1]][j-1],
			pl[i][j]=pl[i][j-1]+pl[p[i][j-1]][j-1];
	dfs(1,0);
	return 0;
}
inline void show(){
	printf("show=====\n");
	for (multiset<int>::iterator it=ans.begin();it!=ans.end();it++)
		printf("%d ",*it);
	printf("\nover=====\n");
}
void work()
{
	T=read();
	printf("%d\n",*ans.begin());
//	show();
	while (T--){
		int x=read(),c=read();
		modify(x,x,col[x],c);
		col[x]=c;
		printf("%d\n",*ans.begin());
//		show();
	}
}
int main()
{
	init();
	work();
	return 0;
}