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