求环套外向树上节点数不小于K的路径数。

 

首先树的话直接点分治+树状数组$O(n\log^2n)$搞定

 

环套树的话，先删掉多余的边(a,b)

然后变成了一棵树，直接点分治

然后在树上找到a到b的路径，将每一棵子树中的点的“所有权”（要么从a出发到达，要么从b出发到达）改变一下，然后计算贡献即可。

总时间复杂度$O(n\log^2n+n\log n)$

 

把BZOJ第700题献给了这道题…

 

#include
     
      #define N 100010typedef long long ll;inline void read(int&a){char c;while(!(((c=getchar())>='0')&&(c<='9')));a=c-'0';while(((c=getchar())>='0')&&(c<='9'))(a*=10)+=c-'0';}int n,m,K,i,x,y,g[N],nxt[N<<1],v[N<<1],ok[N<<1],ed=1,son[N],f[N],size,now,fa[N],exa,exb,to[N],way[N],cnt,in[N],dis[N],t[N],pos;ll ans,bit[N];inline void addedge(int x,int y){v[++ed]=y,nxt[ed]=g[x],ok[ed]=1,g[x]=ed;}int F(int x){return fa[x]==x?x:fa[x]=F(fa[x]);}inline void add(int x){for(;x<=n;x+=x&-x)if(t[x]!=pos)t[x]=pos,bit[x]=1;else bit[x]++;}inline void del(int x){for(;x<=n;x+=x&-x)bit[x]--;}inline ll sum(int x){if(x<0)return 0;ll y=0;for(;x;x-=x&-x)if(t[x]==pos)y+=bit[x];return y;}void findroot(int x,int pre){  son[x]=1;f[x]=0;  for(int i=g[x];i;i=nxt[i])if(ok[i]&&v[i]!=pre){    findroot(v[i],x);    son[x]+=son[v[i]];    if(son[v[i]]>f[x])f[x]=son[v[i]];  }  if(size-son[x]>f[x])f[x]=size-son[x];  if(f[x]