对于一个询问$x$,可以枚举答案$mid$,
将所有大于$mid$的路径填入,如果经过$x$的路径数等于填入路径数,则说明不存在一条路径不经过$x$而$>mid$,因此可以缩小答案的范围,反之亦然成立。
有意思的是求经过$x$的路径数,
首先考虑什么样的路径会经过$x$。
其一头势必经过$x$子树(含$x$)中某一个点,换言之,只有$x$子树中的点可能对当前询问产生贡献。
另一头势必在$x$子树外(含$x$)某一点,换言之,要减去在子树内的不经过$x$的路径数。
因此可以进行差分,每添加一条路径$(x,y)$,$x,y$处$+1$,$lca(x,y),fa(lca(x,y))$处$-1$。
需要时统计$x$子树权之和就是经过$x$的路径数。
整体二分处理一下就就好了。
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<ctime>
#include<algorithm>
#define gc getchar()
#define ll long long
#define ld long double
#define ull unsigned long long
using namespace std;
const int N=1e5+5,M=4e5+5;
template<class o>
inline void qr(o &x)
{
x=0;char c=gc;int f=1;
while(c<'0'||c>'9'){if(c=='-')f=-1;c=gc;}
while(c>='0'&&c<='9'){x=x*10+(c^48);c=gc;}
x*=f;
}
template<class o>
void qw(o x)
{
if(x<0)putchar('-'),x=-x;
if(x/10)qw(x/10);
putchar(x%10+48);
}
struct edge{int y,next;}a[N<<1];int last[N],len;
void ins(int x,int y){a[++len]=(edge){y,last[x]};last[x]=len;}
int siz[N],son[N],fa[N],dep[N];
void dfs1(int x)
{
siz[x]=1;son[x]=0;
for(int k=last[x],y;k;k=a[k].next)
{
if((y=a[k].y)==fa[x])continue;
dep[y]=dep[x]+1;fa[y]=x;
dfs1(y);
siz[x]+=siz[y];if(siz[son[x]]<siz[y])son[x]=y;
}
}
int top[N],dfn[N],yss[N],cnt;
void dfs2(int x,int tp)
{
top[x]=tp;dfn[x]=++cnt;yss[cnt]=x;
if(son[x])dfs2(son[x],tp);
for(int k=last[x],y;k;k=a[k].next)
if((y=a[k].y)!=son[x]&&y!=fa[x])dfs2(y,y);
}
inline int lca(int x,int y)
{
while(top[x]!=top[y])dep[top[x]]>dep[top[y]]?x=fa[top[x]]:y=fa[top[y]];
return dep[x]>dep[y]?y:x;
}
struct node
{
int x,y,f,d,op;
node(int x=0,int y=0,int f=0,int d=0,int op=0):x(x),y(y),f(f),d(d),op(op){}
}s[M],s1[M],s2[M];
int c[N],n,m;
inline void add(int x,int d){for(;x&&x<=n;x+=x&-x)c[x]+=d;}
inline int ask(int x){int ans=0;for(;x;x-=x&-x)ans+=c[x];return ans;}
void modify(int x,int y,int f,int d)//有点难理解,但这样差分是对未来点i,统计其子树权值和时会用到
{
add(dfn[x],d);
add(dfn[y],d);
add(dfn[f],-d);
add(dfn[fa[f]],-d);
}
int query(int x)
{
return ask(dfn[x]+siz[x]-1)-ask(dfn[x]-1);
}
int ans[M];
void div(int l,int r,int L,int R)
{
if(L==R)
{
for(int i=l;i<=r;i++)
if(s[i].op)ans[s[i].op]=L;
return ;
}
int mid=L+R>>1;
int l1=1,r1=0,l2=1,r2=0,sum=0;
for(int i=l;i<=r;i++)
{
if(!s[i].op)
{
if(abs(s[i].d)>mid)
{
if(s[i].d>0)modify(s[i].x,s[i].y,s[i].f,1),++sum;
else modify(s[i].x,s[i].y,s[i].f,-1),--sum;
s2[++r2]=s[i];
}
else s1[++r1]=s[i];
}
else
{
int ss=query(s[i].x);//求子树权值和,若>0,即说明有路径经过。
if(ss==sum)s1[++r1]=s[i];
else s2[++r2]=s[i];
}
}
for(int i=1;i<=r1;i++)s[l+i-1]=s1[i];
for(int i=1;i<=r2;i++)s[l+r1+i-1]=s2[i];
for(int i=1;i<=r2;i++)
if(!s2[i].op)
{
if(s2[i].d>0)modify(s2[i].x,s2[i].y,s2[i].f,-1);
else modify(s2[i].x,s2[i].y,s2[i].f,1);
}
if(l1<=r1)div(l,l+r1-1,L,mid);
if(l2<=r2)div(l+r1,r,mid+1,R);
}
int main()
{
qr(n),qr(m);
for(int i=1,x,y;i<n;i++)qr(x),qr(y),ins(x,y),ins(y,x);
dfs1(1);dfs2(1,1);int qs=0;
for(int i=1;i<=m;i++)
{
int type,x,y,d,t;qr(type);
if(!type)
{
qr(x),qr(y),qr(d);
s[i]=node(x,y,lca(x,y),d,0);
}
else if(type==1)qr(t),s[i]=s[t],s[i].d*=-1;
else qr(x),s[i]=node(x,0,0,0,++qs);
}
div(1,m,0,(int)1e9);
for(int i=1;i<=qs;i++)
qw(ans[i]?ans[i]:-1),puts("");
return 0;
}
最后一次更新于2020-04-01
0 条评论