P3250 [HNOI2016]网络 题解
题面
一个显然的做法是树剖之后dfs序线段树套时间线段树，直接做的复杂度是 \(O(n\log^3 n)\)。其实也可以把询问离线下来，做一个线段树分治，用树套树维护。
这样做比较麻烦，所以考虑另外一种思路：二分答案。因为有很多询问，不妨放在一起二分，所以可以想到整体二分。使用类似树上差分的思想，对于一条路径 \(u\rightarrow lca(u,v)\to v\)，如果它的权值大于 \(mid\)，在用dfs序建的树状数组上给 \(u,v\) 加一，给 \(lca\) 和 \(fa[lca]\) 减一，对于询问统计经过该点的路径条数是否等于此时权值大于 \(mid\) 的路径数量，向两边递归即可。
这道题还有使用路径交等一系列科技的 \(1\log\) 做法，太神了本人（当时可能）并不会……然而现在估计也不会。
点击查看代码
#include
#include
#include
inline int max(const int &a,const int &b){return a>b?a:b;}
inline void swap(int &x,int &y){x^=y^=x^=y;}
inline int rd(){
int res=0;char c=getchar();
for(;!isdigit(c);c=getchar());
for(;isdigit(c);c=getchar())res=(res<<1)+(res<<3)+(c-'0');
return res;
}
void wt(int x){if(x<0){putchar('-'),wt(-x);return;}if(x>9)wt(x/10);putchar(x%10+'0');}
const int N=2e5+13;
struct Node{
int op,u,v,t,x,id,ans;
bool operator <(const Node &a)const{return idmaxson) maxson=siz[v],son[u]=v;
}
dfnr[u]=++dfs_clock;
}
void dfs2(int u,int topf){
top[u]=topf;
if(!son[u]) return;
dfs2(son[u],topf);
for(int i=h[u];i;i=e[i].nxt){
int v=e[i].v;
if(v!=fa[u]&&v!=son[u]) dfs2(v,v);
}
}
inline int lca(int u,int v){
while(top[u]!=top[v]){
if(dep[top[u]]r) return;
if(L==R){
for(int i=l;i<=r;++i)
if(q[i].op==2) q[i].ans=L;
return;
}
int mid=(L+R)>>1,lt=0,rt=0,tmp=0;
for(int i=l;i<=r;++i){
if(q[i].op!=2){
if(q[i].x<=mid) lq[++lt]=q[i];
else{
int v=(q[i].op?-1:1);tmp+=v;
if(q[i].u&&q[i].v) T.add(dfnl[q[i].u],v),T.add(dfnl[q[i].v],v),T.add(dfnl[q[i].t],-v);
if(fa[q[i].t]) T.add(dfnl[fa[q[i].t]],-v);
rq[++rt]=q[i];
}
}
else{
if(T.sum(dfnr[q[i].x])-T.sum(dfnl[q[i].x]-1)==tmp) lq[++lt]=q[i];
else rq[++rt]=q[i];
}
}
for(int i=l;i<=r;++i){
if(q[i].op==2||q[i].x<=mid) continue;
int v=(q[i].op?1:-1);
T.add(dfnl[q[i].u],v),T.add(dfnl[q[i].v],v),T.add(dfnl[q[i].t],-v);
if(fa[q[i].t]) T.add(dfnl[fa[q[i].t]],-v);
}
for(int i=1;i<=lt;++i) q[l+i-1]=lq[i];
for(int i=1;i<=rt;++i) q[l+lt+i-1]=rq[i];
solve(L,mid,l,l+lt-1);
solve(mid+1,R,l+lt,r);
}
int main(){
n=rd(),m=rd();
for(int i=1,u,v;i