LINK:网络
一棵树 每次添加一条路径 或者删除之前的一条路径 或询问除了不经过某个点之外剩下的最大值。
一个显然的思路 对于一条路径的权值我们直接把权值塞上去 标记永久化一下即可。
考虑如何求答案 一个比较暴力的思想 我们取所某个节点的所有标记 和全局标记从小到大一一比对即可。
这样复杂度还是Q^2的.
可以发现对于一条链的权值 如果不放到链上 而是放到这条链之外的所有的点上 那么我们求答案其实就变成了单点查询。
可以在树剖的时候把要覆盖的链求出来 排个序就得到了补集。(不过这种做法nlog^3 慢了。
还可以优化一下第一种一一比对的做法 直接主席树上二分 因为某个点的所有主席树的并是全集的子集 可以发现这样做事正确的。
但是复杂度是nlog^3(太慢了。有一说一 这里采用树状数组套主席树也行。
删除也好删除主席树上删即可 比堆删要快一点 不过太慢了。
杀器二分。考虑二分 然后就变成了多有>=mid的路径是否都经过了这个点 暴力扫。
复杂度Q^2log 绝杀 一个整体二分,Qlog^2 但是需要解决的问题是 区间赋值单点查询 又回到树剖了么？
考虑树上差分一下 我们只需要维护子树和即可 这样一个log即可。
最终还是建议使用整体二分来做 第一种方法 容易RE什么的常数大 第二种方法就是常数大 第三种方法码量小 常数小 空间小的多。
说一句闲话 没必要O(1)LCA 因为询问Q个我们预处理一下即可。(但是O(1)LCA没倍增写的多 还是写一下吧.
const int MAXN=200010;
int n,Q,cnt,top,num,cc,len;
struct wy
{
int op,x,y,z;
}t[MAXN],tl[MAXN],tr[MAXN];
int dfn[MAXN],f[MAXN][20],Log[MAXN],fir[MAXN],ans[MAXN],c[MAXN];
int lin[MAXN],ver[MAXN],nex[MAXN],d[MAXN],b[MAXN],fa[MAXN],sz[MAXN];
inline int cmp(int x,int y){return d[x]<d[y]?x:y;}
inline void add(int x,int y)
{
ver[++len]=y;nex[len]=lin[x];lin[x]=len;
ver[++len]=x;nex[len]=lin[y];lin[y]=len;
}
inline void dfs(int x,int father)
{
dfn[x]=++cnt;fir[x]=++top;d[x]=d[father]+1;sz[x]=1;
f[top][0]=x;Log[top]=Log[top>>1]+1;fa[x]=father;
go(x)
{
if(tn==father)continue;
dfs(tn,x);
f[++top][0]=x;Log[top]=Log[top>>1]+1;
sz[x]+=sz[tn];
}
}
inline int LCA(int x,int y)
{
x=fir[x];y=fir[y];
if(x>y)swap(x,y);
int w=Log[y-x+1];
return cmp(f[x][w],f[y-(1<<w)+1][w]);
}
inline void discrete()
{
sort(b+1,b+1+cnt);
rep(1,cnt,i)if(i==1||b[i]!=b[i-1])b[++num]=b[i];
rep(1,Q,i)if(op(i)!=2)z(i)=lower_bound(b+1,b+1+num,z(i))-b;
}
inline void add1(int x,int y)
{
if(!x)return;
//cout<<x<<endl;
while(x<=n)
{
c[x]+=y;
x+=x&(-x);
}
}
inline int ask(int x){int cnt=0;while(x)cnt+=c[x],x-=x&(-x);return cnt;}
inline int ask(int x,int y){return ask(y)-ask(x-1);}
inline void solve(int l,int r,int L,int R)
{
if(l>r)return;
if(L==R)
{
rep(l,r,i)if(op(i)==2)ans[z(i)]=L;
return;
}
int mark=0,ql=0,qr=0,mid=(L+R)>>1,ww=0;
rep(l,r,i)
{
if(op(i)!=2)
{
if(z(i)>mid)
{
tr[++qr]=t[i];int lca=LCA(x(i),y(i));ww+=op(i);
add1(dfn[x(i)],op(i));add1(dfn[y(i)],op(i));
add1(dfn[lca],-op(i));add1(dfn[fa[lca]],-op(i));
}
else tl[++ql]=t[i];
}
else
{
int w=ask(x(i),y(i));
if(w==ww)tl[++ql]=t[i];
else tr[++qr]=t[i];
mark=1;
}
}
rep(1,qr,i)if(tr[i].op!=2&&tr[i].z>mid)
{
int lca=LCA(tr[i].x,tr[i].y);
add1(dfn[tr[i].x],-tr[i].op);add1(dfn[tr[i].y],-tr[i].op);
add1(dfn[lca],tr[i].op);add1(dfn[fa[lca]],tr[i].op);
}
if(!mark)return;
rep(1,ql,i)t[l+i-1]=tl[i];
rep(1,qr,i)t[l+ql+i-1]=tr[i];
solve(l,l+ql-1,L,mid);solve(l+ql,r,mid+1,R);
}
int main()
{
freopen("1.in","r",stdin);
get(n);get(Q);Log[0]=-1;
rep(2,n,i)add(read(),read());
dfs(1,0);cnt=0;
rep(1,Log[top],j)rep(1,top-(1<<j)+1,i)
{
f[i][j]=cmp(f[i][j-1],f[i+(1<<(j-1))][j-1]);
//cout<<cmp(f[i][j-1],f[i+(1<<(j-1))][j-1])<<' '<<f[i][j-1]<<' '<<f[i+(1<<(j-1))][j-1]<<endl;
}
rep(1,Q,i)
{
get(op(i));
if(op(i)==0)
{
get(x(i));get(y(i));get(z(i));
b[++cnt]=z(i);op(i)=1;
continue;
}
if(op(i)==1)
{
int w;get(w);
x(i)=x(w);y(i)=y(w);z(i)=z(w);
//cout<<x(i)<<' '<<y(i)<<endl;
op(i)=-1;
}
if(op(i)==2)
{
int w;get(w);
x(i)=dfn[w];
y(i)=x(i)+sz[w]-1,z(i)=++cc;
}
}
discrete();
solve(1,Q,0,num);b[0]=-1;
rep(1,cc,i)put(b[ans[i]]);
return 0;
}
我收回之前说的话 这个东西难写+难调 写+调了2h才搞出来 细节贼多。
线段树+堆要好写多了。自闭了。