东莞规划局官方网站,住房和建设厅网站,重庆建工信息网官网,郴州网站建设制作首先#xff0c;我们求出树的重链#xff0c;然后对于每一条链#xff0c;建一颗线段树 树大概长这样#xff1a; #xff08;其中用红边连起来的是一条条重链#xff09; 在线段树上#xff0c;我们维护#xff1a; Opt(u)#xff1a;经过 u节点代表的链的其中一段 …首先我们求出树的重链然后对于每一条链建一颗线段树 树大概长这样 其中用红边连起来的是一条条重链 在线段树上我们维护 Opt(u)经过 u节点代表的链的其中一段 的两个白点间的最长路径长度 MaxL(u)u节点代表的链的左端点到最远的白点的距离 MaxR(u)u节点代表的链的右端点到最远的白点的距离 怎么维护呢 我们再定义一些辅助变量方便描述 D(i)节点i到最远的白点的距离 D2(i)节点i到次远的白点的距离 Dist(x,y)节点x,y之间的距离 Lc线段树上左儿子 Rc线段树上右儿子 当 lr 即链只有一个节点时 若u为黑色 MaxL(u)MaxR(u)D(L) Opt(u)D(L)D2(L) 若u为白色 MaxL(u)MaxR(u)Max{D(L),0} Opt(u)Max{D(L)D2(L),D(L)} 然后考虑如何push_up MaxL(u)Max{MaxL(Lc),Dist(L,mid1)MaxL(Rc)} MaxR(u)Max{MaxR(Rc),Dist(mid,R)MaxR(Lc)} Opt(u)Max{Opt(Lc),Opt(Rc),MaxR(Lc)MaxL(Rc)Dist(mid,mid1)} 这样我们就维护好线段树啦接下来考虑怎么在树上修改一个点的颜色 假设我们要修改黄色点的颜色那么我们肯定要修改被黄色笔框住的这条链 然后蓝色点肯定也被影响了所以我们接下来修改被蓝色笔框住的这条链 再接下来绿色点也被影响力所以我们修改被绿色笔框住的这条链 而下面已经没有点被影响了修改结束 可见要修改一个点我们只需要一层层链跳上去直到当前的链头无父节点为止 然后我们还要考虑一下如何维护D(i)和D2(i) (节点到最远和次远白点的距离) 对此我们对每个点维护一个大根堆记录这个点到每个白点的距离 D(i)s.top(); s.pop(); D2(i)s.top(); s.push(D(i)); 这样就可以求出D(i)和D2(i)啦 最后在全局用个堆维护每条链的Opt就可以直接查询了 这是Query on a tree IV的代码
#includeiostream
#includecstdio
#includecstring
#includequeue
using namespace std;
const int maxn100005;
const int inf1e9;
struct work{priority_queue int f,g;inline void ins(int v) { if(v ! -inf) f.push(v); } inline void era(int v) { if(v ! -inf) g.push(v); }inline int top() {while(1){if(f.empty()) return -inf;if(g.empty()) return f.top();if(f.top() g.top()) f.pop(), g.pop();else return f.top();}}
}h[maxn], ans;
struct Edge{int u,v,w,next;
}edge[maxn1];
struct seg{int l,r,v,ls,rs;
}st[maxn2];
int wn,n,m,head[maxn],cnt,col[maxn],rt[maxn],onp;
int sz[maxn],fa[maxn],dep[maxn],son[maxn];
int tid[maxn],ord[maxn],ind,top[maxn],len[maxn];
inline int read() {int p0,w1; char chgetchar();while(ch9||ch0) {if(ch-) w -1; chgetchar();}while(ch0ch9) pp*10ch-0,chgetchar();return p*w;
}
void add(int u,int v,int w){edge[cnt].uu;edge[cnt].vv;edge[cnt].ww;edge[cnt].nexthead[u];head[u]cnt;
}
#define dis(x) dep[ord[x]]
void push(int u,int l,int r){int lsst[u].ls,rsst[u].rs,mid(lr)1;st[u].lmax(st[ls].l,st[rs].ldis(mid1)-dis(l));//MaxL(u)Max{MaxL(Lc),Dist(L,mid1)MaxL(Rc)}st[u].rmax(st[rs].r,st[ls].rdis(r)-dis(mid));//MaxR(u)Max{MaxR(Rc),Dist(mid,R)MaxR(Lc)}st[u].vmax(max(st[ls].v,st[rs].v),st[ls].rst[rs].ldis(mid1)-dis(mid));//Opt(u)Max{Opt(Lc),Opt(Rc),MaxR(Lc)MaxL(Rc)Dist(mid,mid1)}
}
void build(int u,int l,int r){if(!u) uonp;if(lr){int xord[l];for(int ihead[x];i!-1;iedge[i].next){int vedge[i].v;if(vfa[x]||vson[x]) continue;h[x].ins(st[rt[v]].ldep[v]-dep[x]);}int d1h[x].top(); h[x].era(d1); int d2h[x].top(); h[x].ins(d1);st[u].lst[u].rmax(d1,0); st[u].vmax(0,max(d1,d1d2));//Opt(u)Max{D(L)D2(L),D(L)} 白色 return;}int mid (lr)1;build(st[u].ls,l,mid);build(st[u].rs,mid1,r);push(u,l,r);
}
void update(int u,int l,int r,int v,int s){if(lr){if(vs){int d1h[v].top();h[v].era(d1); int d2 h[v].top(); h[v].ins(d1);if(col[v]) st[u].lst[u].rd1,st[u].vd1d2;//OptD(L)D2(L) 黑色 else st[u].lst[u].rmax(d1,0),st[u].vmax(0,max(d1,d1d2));//Opt(u)Max{D(L)D2(L),D(L)} 白色 }else{h[v].ins(st[rt[s]].ldep[s]-dep[v]);int d1 h[v].top(); h[v].era(d1);int d2 h[v].top(); h[v].ins(d1);if(col[v]) st[u].lst[u].rd1,st[u].vd1d2;//OptD(L)D2(L) 黑色 else st[u].lst[u].rmax(d1,0),st[u].vmax(0,max(d1,d1d2));//Opt(u)Max{D(L)D2(L),D(L)} 白色 }return;}int mid(lr)1;if(tid[v]mid) update(st[u].ls,l,mid,v,s);else update(st[u].rs,mid1,r,v,s);push(u,l,r);
}
void dfs1(int u){sz[u]1;for(int ihead[u];i!-1;iedge[i].next){int vedge[i].v;int wedge[i].w;if(vfa[u]) continue;fa[v]u; dep[v]dep[u]w;dfs1(v);sz[u]sz[v];if(sz[v]sz[son[u]]) son[u]v;}
}
void dfs2(int u,int tp){tid[u]ind;top[u]tp;ord[ind]u;len[tp];if(!son[u]) return;dfs2(son[u],tp);for(int ihead[u];i!-1;iedge[i].next){int vedge[i].v;if(vfa[u]||vson[u]) continue;dfs2(v,v);}
}
int main(){ios::sync_with_stdio(false);memset(head,-1,sizeof(head));wnnread();int u,v,w;for(int i1;in;i){uread();vread();wread();add(u,v,w);add(v,u,w);}dfs1(1);dfs2(1,1);ans.ins(0);for(int in;i;i--){int uord[i]; if(u!top[u]) continue; build(rt[u],tid[u],tid[u]len[u]-1); //每一条链建一线段树 ans.ins(st[rt[u]].v);}mread();char ch;for(int i1;im;i){chgetchar();while(ch!Cch!A) chgetchar();if(chC){int xread(); col[x]^ 1;if(col[x]0) wn; else wn --;for(int ux,pu;u;ufa[u]){int tptop[u];int p1st[rt[tp]].v,d1st[rt[tp]].l;if(fa[tp]) h[fa[tp]].era(st[rt[tp]].ldep[tp]-dep[fa[tp]]);update(rt[tp],tid[tp],tid[tp]len[tp]-1,u,p);int p2st[rt[tp]].v,d2st[rt[tp]].l;if(p1!p2) ans.era(p1),ans.ins(p2);putp;}}else {if(wn0) printf(They have disappeared.\n);else printf(%d\n, ans.top());}}return 0;
}捉迷藏的代码只需要改一下输入输出就不贴了
