第一次写维护点分治的树
然后因为大错一个数字调了半个小时是在蛋疼，最近开的坑太多赶脚没有时间填了
算了一点点来吧
//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;
}
