给定一棵n个点的树,有m次操作
1.加入权值为w的一条链
2.删除之前的一条链
3.求不经过某个点的所有链中的最大权值
\(n \le 10^5\)
Solution:暴力方法\(nlog^3n\)过掉了?
首先考虑转化,一条链会对所有不在链上的点产生贡献 (这里没想到)
每次暴力更新,最多\(log\)个区间
由于要删除,我们可以用线段树套可删除堆
所以修改的总复杂度是\(nlog^3n\)
查询的话就单点查询,要考虑沿途答案
#include <map> #include <set> #include <stack> #include <cmath> #include <queue> #include <cstdio> #include <cstring> #include <cstdlib> #include <iostream> #include <algorithm> #define ls p<<1 #define rs p<<1|1 using namespace std; typedef long long ll; const int mxn=2e5+5; int n,m,df,cnt,tot,hd[mxn]; int f[mxn],rk[mxn],sz[mxn],dep[mxn],dfn[mxn],top[mxn],son[mxn]; inline int read() { char c=getchar(); int x=0,f=1; while(c>'9'||c<'0') {if(c=='-') f=-1;c=getchar();} while(c<='9'&&c>='0') {x=(x<<3)+(x<<1)+(c&15);c=getchar();} return x*f; } inline void chkmax(int &x,int y) {if(x<y) x=y;} inline void chkmin(int &x,int y) {if(x>y) x=y;} struct Tree { priority_queue<int > q1,q2; int top() { while(!q1.empty()&&!q2.empty()&&q1.top()==q2.top()) q1.pop(),q2.pop(); if(q1.empty()) return -1; else return q1.top(); } void push(int x) { q1.push(x); } void pop(int x) { q2.push(x); } }tr[mxn<<2]; struct M { int u,v,w; }mis[mxn]; struct Q { int l,r; }q[mxn]; struct ed { int to,nxt; }t[mxn<<1]; int cmp(Q x,Q y) { return x.l<y.l; } inline void add(int u,int v) { t[++cnt]=(ed) {v,hd[u]}; hd[u]=cnt; } void dfs1(int u,int fa) { f[u]=fa; sz[u]=1; dep[u]=dep[fa]+1; for(int i=hd[u];i;i=t[i].nxt) { int v=t[i].to; if(v==fa) continue ; dfs1(v,u); sz[u]+=sz[v]; if(sz[son[u]]<sz[v]) son[u]=v; } } void dfs2(int u,int tp) { dfn[u]=++df; rk[df]=u; top[u]=tp; if(son[u]) dfs2(son[u],tp); for(int i=hd[u];i;i=t[i].nxt) { int v=t[i].to; if(v==f[u]||v==son[u]) continue ; dfs2(v,v); } } void update(int l,int r,int ql,int qr,int val,int opt,int p) { if(qr<1||ql>n) return ; if(ql<=l&&r<=qr) { if(opt) tr[p].push(val); else tr[p].pop(val); return ; } int mid=(l+r)>>1; if(ql<=mid) update(l,mid,ql,qr,val,opt,ls); if(qr>mid) update(mid+1,r,ql,qr,val,opt,rs); } int query(int l,int r,int pos,int p) { if(l==r) return tr[p].top(); int mid=(l+r)>>1; if(pos<=mid) return max(tr[p].top(),query(l,mid,pos,ls)); else return max(tr[p].top(),query(mid+1,r,pos,rs)); } void modify(int x,int y,int w,int opt) { tot=0; while(top[x]!=top[y]) { if(dep[top[x]]<dep[top[y]]) swap(x,y); q[++tot]={dfn[top[x]],dfn[x]}; x=f[top[x]]; } if(dep[x]<dep[y]) swap(x,y); q[++tot]=(Q){dfn[y],dfn[x]}; sort(q+1,q+tot+1,cmp); update(1,n,1,q[1].l-1,w,opt,1); for(int i=1;i<tot;++i) update(1,n,q[i].r+1,q[i+1].l-1,w,opt,1); update(1,n,q[tot].r+1,n,w,opt,1); } int main() { n=read(); m=read(); int u,v,w,opt; for(int i=1;i<n;++i) { u=read(); v=read(); add(u,v); add(v,u); } dfs1(1,0); dfs2(1,1); for(int i=1;i<=m;++i) { opt=read(); if(opt==0) { u=read(); v=read(); w=read(); mis[i]=(M){u,v,w}; modify(u,v,w,1); } else if(opt==1) u=read(),modify(mis[u].u,mis[u].v,mis[u].w,0); else { u=read(); v=query(1,n,dfn[u],1); printf("%d\n",v); } } return 0; }