「HNOI2016」网络
我有一个绝妙的可持久化树套树思路，可惜的是，它的空间是\(n\log^2 n\)的...
注意到对一个询问，我们可以二分答案
然后统计经过这个点大于当前答案的路径条数，如果这个路径条数等于大于当前答案的所有路径条数，那么这个答案是不行的。
关于链修改单点询问，可以树状数组维护dfs序，然后每次修改链去差分修改
然后把二分答案拿到整体二分上去就可以了
Code:
#include <cstdio>
#include <cctype>
#include <cmath>
#include <algorithm>
const int N=3e5+10;
template <class T>
void read(T &x)
{
x=0;char c=getchar();
while(!isdigit(c)) c=getchar();
while(isdigit(c)) x=x*10+c-'0',c=getchar();
}
int head[N],to[N<<1],Next[N<<1],cnt;
void add(int u,int v)
{
to[++cnt]=v,Next[cnt]=head[u],head[u]=cnt;
}
int dfn[N],low[N],dep[N],f[18][N],dfsclock;
int n,m,q,s[N],ans[N];
struct koito_yuu{int u,v,x,lca;}yuu[N],yuul[N],yuur[N];
void dfs(int now)
{
dfn[now]=++dfsclock;
dep[now]=dep[f[0][now]]+1;
for(int i=1;f[i-1][now];i++) f[i][now]=f[i-1][f[i-1][now]];
for(int v,i=head[now];i;i=Next[i])
if((v=to[i])!=f[0][now])
f[0][v]=now,dfs(v);
low[now]=dfsclock;
}
int LCA(int x,int y)
{
if(dep[x]<dep[y]) std::swap(x,y);
for(int i=17;~i;i--)
if(dep[f[i][x]]>=dep[y])
x=f[i][x];
if(x==y) return x;
for(int i=17;~i;i--)
if(f[i][x]!=f[i][y])
x=f[i][x],y=f[i][y];
return f[0][x];
}
void modify(int x,int d){while(x&&x<=n)s[x]+=d,x+=x&-x;}
int query(int x){int ret=0;while(x)ret+=s[x],x-=x&-x;return ret;}
void modi(int u,int v,int lca,int d)
{
modify(dfn[u],d);
modify(dfn[v],d);
modify(dfn[lca],-d);
modify(dfn[f[0][lca]],-d);
}
int qry(int u)
{
return query(low[u])-query(dfn[u]-1);
}
void Divide(int l,int r,int L,int R)
{
if(l>r) return;
if(L==R)
{
for(int i=l;i<=r;i++)
if(!yuu[i].v)
ans[yuu[i].x]=L;
return;
}
int Mid=L+R>>1;
int lp=0,rp=0,cnt=0;
for(int i=l;i<=r;i++)
{
if(yuu[i].v)
{
if(abs(yuu[i].x)>Mid)
{
yuur[++rp]=yuu[i];
if(yuu[i].x>0) modi(yuu[i].u,yuu[i].v,yuu[i].lca,1),++cnt;
else modi(yuu[i].u,yuu[i].v,yuu[i].lca,-1),--cnt;
}
else yuul[++lp]=yuu[i];
}
else
{
int ct=qry(yuu[i].u);
if(ct==cnt) yuul[++lp]=yuu[i];
else yuur[++rp]=yuu[i];
}
}
for(int i=l;i<=r;i++)
if(yuu[i].v&&abs(yuu[i].x)>Mid)
modi(yuu[i].u,yuu[i].v,yuu[i].lca,yuu[i].x>0?-1:1);
for(int i=1;i<=lp;i++) yuu[i+l-1]=yuul[i];
for(int i=1;i<=rp;i++) yuu[i+l+lp-1]=yuur[i];
Divide(l,l+lp-1,L,Mid),Divide(l+lp,r,Mid+1,R);
}
int main()
{
read(n),read(m);
for(int u,v,i=1;i<n;i++) read(u),read(v),add(u,v),add(v,u);
dfs(1);
for(int typ,t,i=1;i<=m;i++)
{
read(typ);
if(typ==0) read(yuu[i].u),read(yuu[i].v),read(yuu[i].x),yuu[i].lca=LCA(yuu[i].u,yuu[i].v);
else if(typ==1) read(t),yuu[i]=yuu[t],yuu[i].x=-yuu[i].x;
else read(yuu[i].u),yuu[i].x=++q;
}
Divide(1,m,0,(int)(1e9));
for(int i=1;i<=q;i++) printf("%d\n",ans[i]?ans[i]:-1);
return 0;
}
2019.3.9