为啥说是小结。。这辣鸡题我写了两天。 （顺带其中参观了一下SCOI的大新闻）
这题思路首先是树剖，剖出来之后，考虑对于每个点维护一个d1,d2,表示从这个点往下走，不经过自己所在重链的边，到达一个黑点的最长路径和次长路径。如果下面黑点不足就是-INF了。
处理出来之后，对于一条链，线段树维护这么几个值， lv:表示其中一个黑点走到左端点的最长距离 rv:同上，走到右端点 v:其中两个黑点的最长路径。
然后处理一个树上路径前缀和，sum[i]表示根到i的距离。 (lc代表左儿子,rc代表右儿子,窝用的是指针可能会有点鬼畜) (suml表示左儿子那个区间的路径和，sumr表示右儿子路径和，L表示中间那条边长度）
转移的话 lv=max(lc->lv,suml+L+rc->lc) rv=max(rc->rv,sumr+L+lc->rv) v=max{lc->v,rc->v,lc->rv+L+rc->lv} //是不是觉得跟最大连续子段和一毛一样呀
对于边界，也就是一个点的情况 如果是黑点 lv=rv=max(0,d1) 否则 lv=rv=d1 如果是黑点 v=max(d1,d1+d2) 否则 v=d1+d2
然后就维护好了。
考虑来怎么维护这个d啊， ‘ 我是这样做的啊，solve一条链的方法是，从上往下遍历链的每个点u，然后solve u可以遍历到的非当前链节点v，然后这个函数返回这条链的lv(就是上面提到的lv)，然后把lv加上w(u,v)扔进堆，最后取前两个。
然后也维护好了啊。
怎么回答呢，，我当时比较zz，把每条链的v扔进一个堆然后query的时候直接取堆顶。
修改怎么搞，，先找到点所在的链，线段树上update一下这条链的v，然后往上爬直到根节点。因为下面的节点颜色变了，上面的节点的d1,d2要重算，幸运的是需要重算的链的数量不超过logn条，一次update复杂度为logn，机智的同学会发现为了维护新的d1,d2可能需要删除之前的一些信息（毕竟有点的颜色变了），需要从堆里删去一个值，然后就变成用set维护了（也许常数比较大）
这题细节比较多强烈建议跟暴力拍。不过不要像我一样，暴力数组开小了，还在疑惑为什么一拍大数据就WA。
（有点像wrs讲的维护信息的题目，线段树主要就是能维护信息，信息能合并，于是可以定义data来表示信息，重载+或者写一个merge函数，在up和query的时候都会用到（这个题调的欲仙欲死,好久没写4k+代码咯））
//QWsin #include<set> #include<cmath> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; const int maxn=100000+10; const int maxm=200000+10; template <typename T> struct CMP{ bool operator ()(const T &l,const T &r){return l>r;} }; multiset<int,CMP<int> >topval,f[maxn]; struct Edge{int u,v,w;Edge(int u=0,int v=0,int w=0):u(u),v(v),w(w){}}e[maxm]; int first[maxn],Next[maxm],ecnt; inline void add_edge(int u,int v,int w){ Next[ecnt]=first[u];first[u]=ecnt;e[ecnt++]=Edge(u,v,w); Next[ecnt]=first[v];first[v]=ecnt;e[ecnt++]=Edge(v,u,w); } int sum[maxn];//树上路径前缀和 struct Data{ int lv,rv,v; Data(){lv=rv=v=0;} inline void init(){lv=rv=v=0;} }; inline Data add(const Data &a,const Data &b,int L,int suml,int sumr){ Data ret; ret.v=max(max(a.v,b.v),a.rv+b.lv+L); ret.lv=max(a.lv,suml+L+b.lv); ret.rv=max(b.rv,sumr+L+a.rv); return ret; } struct Node{ Data t;Node *lc,*rc; Node(){t.init();lc=rc=NULL;} }*root; #define mid ((l+r)>>1) int n,iid[maxn],col[maxn]; int sz[maxn],fa[maxn],tid[maxn],hv[maxn],top[maxn],dn[maxn],dep[maxn]; const int INF=1<<28; inline void work(Node* p,int u)//用f[u]的信息更新u单点的信息 { int d1,d2;d1=d2=-INF; if(col[u]) d1=d2=0; if(f[u].size()) d1=max(d1,*f[u].begin()); if(f[u].size() > 1) d2=max(d2,*(++f[u].begin())); p->t.lv=p->t.rv=d1; if(col[u]) p->t.v=max(d1,d1+d2); else p->t.v=d1+d2; } void build(Node* &p,int l,int r) { p=new Node();if(l==r) return ; build(p->lc,l,mid);build(p->rc,mid+1,r); } void updata(Node* p,int l,int r,int pos)//先在线段树上找到那个节点再用set来更新 { if(l==r) {work(p,iid[pos]);return ;} if(pos<=mid) updata(p->lc,l,mid,pos); else updata(p->rc,mid+1,r,pos); p->t=add(p->lc->t , p->rc->t , sum[iid[mid+1]]-sum[iid[mid]],sum[iid[mid]]-sum[iid[l]],sum[iid[r]]-sum[iid[mid+1]]); } Data query(Node* p,int l,int r,int L,int R) { if(L<=l&&r<=R) return p->t; if(mid<L) return query(p->rc,mid+1,r,L,R); else if(R<=mid) return query(p->lc,l,mid,L,R); else return add(query(p->lc,l,mid,L,R),query(p->rc,mid+1,r,L,R),sum[iid[mid+1]]-sum[iid[mid]],sum[iid[mid]]-sum[iid[max(L,l)]],sum[iid[min(R,r)]]-sum[iid[mid+1]]); } void dfs1(int u,int pre,int dis=0) { fa[u]=pre;sz[u]=1;dep[u]=dep[pre]+1; sum[u]=dis; int M=0; for(int i=first[u];i!=-1;i=Next[i]) { int v=e[i].v; if(v==pre) continue; dfs1(v,u,dis+e[i].w); sz[u]+=sz[v];if(sz[v] >= M) {M=sz[v];hv[u]=v;} } } int node_cnt; void dfs2(int u,int Top) { top[u]=Top;tid[u]=++node_cnt; iid[node_cnt]=u; if(dep[u] > dep[dn[Top]]) dn[Top]=u; if(sz[u]==1) return ; dfs2(hv[u],Top); for(int i=first[u];i!=-1;i=Next[i]) if(e[i].v!=fa[u]&&e[i].v!=hv[u]) dfs2(e[i].v,e[i].v); } int cntb; inline void output(multiset<int,CMP<int> >&s){ for(multiset<int,CMP<int> >::iterator it=s.begin();it!=s.end();++it){ printf("%d ",*it); } puts("\n"); } inline int solve_top(int Top)//计算以Top为top的重链 { for(int u=Top;;u=hv[u])//沿着重儿子往下跳 { for(int i=first[u];i!=-1;i=Next[i]) { int v=e[i].v; if(v==fa[u]||v==hv[u]) continue; int tmp=solve_top(v); f[u].insert(tmp+e[i].w); } updata(root,1,n,tid[u]); if(sz[u]==1) break; } Data ret=query(root,1,n,tid[Top],tid[dn[Top]]); topval.insert(ret.v); // output(topval); return ret.lv; } inline void init_data() { cin>>n;memset(first,-1,sizeof first); for(int i=1,u,v,w;i<n;++i){scanf("%d%d%d",&u,&v,&w);add_edge(u,v,w); } for(int i=1;i<=n;++i) col[i]=1;cntb=n; dfs1(1,1);dfs2(1,1); build(root,1,n); solve_top(1); // output(topval); } inline int query(){ return *topval.begin(); } inline Data query(int pos){//询问pos所在链的ans return query(root,1,n,tid[top[pos]],tid[dn[top[pos]]]); } inline void updata(int pos) { int to=fa[top[pos]]; Data tmp=query(pos); topval.erase(topval.find(tmp.v)); if(top[pos]!=1) f[to].erase(f[to].find(tmp.lv+sum[top[pos]]-sum[to])); updata(root,1,n,tid[pos]); tmp=query(pos); topval.insert(tmp.v); if(top[pos]==1) return ; f[to].insert(tmp.lv+sum[top[pos]]-sum[to]); updata(to); } inline void solve() { int m;cin>>m; char op[5];int a; while(m--) { scanf("%s",op); if(op[0]=='A') { if(cntb==0) {puts("They have disappeared.");continue;} if(cntb==1) {puts("0");continue;} printf("%d\n",query()); } else { scanf("%d",&a); if(!col[a]) ++cntb; else --cntb; col[a]^=1; updata(a); // output(topval); } } } int main() { init_data(); solve(); return 0; }