poj1208，【POJ1741】Tree，第一次的点分治

Time:2016.08.04
Author:xiaoyimi
转载注明出处谢谢

注意：代码中递归子树时对子树大小的计算有误,虽然可以保证正确性但是会使得求得的子树重心并不正确,可能会被卡掉


传送门
思路
考虑节点x为根时
$ans_x=Σ(i,j)[i,j∈x的不同子树上的节点]+Σ(i,j)[i,j∈x的相同子树上的节点]$
可以发现，前一项我们可以通过各节点到x的距离直接求出来，具体做法是做一遍dfs，求得节点与x的距离dis，然后将所有dis排序，O(n)求得（这个比较简单，我就不详细说了）
但这种方法同时也会把相同子树上的节点当成点对算进去，这里面可能有不满足条件的点对，也会让后面的点对重复计算，所以要去掉，具体做法是用相同的方法再计算一遍x的各子树上的$\sum ans_i[i∈x的子节点]$，用$ans_x$减去即可
即我们要求的最终答案为$tot_x=ans_x-\sum ans_i[i∈x的子节点]$
后一项实际上就是各个节点的tot，即$\sum tot_i[i∈x的子节点$
显然这是可以递归分治求和的
复杂度是神奇的$O(nlog^2n)$
注意：
每次寻找完重心后dis都会改变（这里的dis[i]实际上是i到当前处理的子树的根的距离）
不要全局记录fa
访问的点打标记blabla
话说点分……慢慢来嘛
代码：

#include<cstdio>
#include<algorithm>
#define M 40004
#define LL long long
using namespace  std;
int in()
{int t=0;char ch=getchar();while (ch<'0'||ch>'9') ch=getchar();while (ch>='0'&&ch<='9') t=(t<<1)+(t<<3)+ch-48,ch=getchar();return t;
}
int n,k,tot,G;
LL ans;
int first[M],siz[M],dis[M],mx[M];
bool vis[M];
struct edge{int u,v,w,next;
}e[M<<1];
void add(int z,int x,int y)
{e[++tot]=(edge){x,y,z,first[x]};first[x]=tot;e[++tot]=(edge){y,x,z,first[y]};first[y]=tot;
}
void dfs(int x,int S,int fa)
{siz[x]=1;mx[x]=0;for (int i=first[x];i;i=e[i].next)if (!vis[e[i].v]&&fa!=e[i].v)dfs(e[i].v,S,x),siz[x]+=siz[e[i].v],mx[x]=max(mx[x],siz[e[i].v]);mx[x]=max(mx[x],S-siz[x]);if (mx[G]>mx[x]) G=x;
}
void form(int x,int D,int fa)
{dis[++dis[0]]=D;for (int i=first[x];i;i=e[i].next)if (!vis[e[i].v]&&fa!=e[i].v)form(e[i].v,D+e[i].w,x);
}
LL cal(int x,int D)
{dis[0]=0;form(x,D,0);LL sum=0;sort(dis+1,dis+dis[0]+1);int l=1,r=dis[0];for (;l<r;)if (dis[l]+dis[r]<=k)sum+=r-l,l++;else r--;return sum;
}
void solve(int x,int S)
{G=0;dfs(x,S,0);x=G;S=siz[x];vis[x]=1;ans+=cal(x,0);for (int i=first[x];i;i=e[i].next)if (!vis[e[i].v])ans-=cal(e[i].v,e[i].w);for (int i=first[x];i;i=e[i].next)if (!vis[e[i].v]) solve(e[i].v,siz[e[i].v]);
}
main()
{mx[0]=M;for (;;){n=in();k=in();if (!n&&!k) break;tot=0;for (int i=1;i<=n;i++) vis[i]=first[i]=0;for (int i=1;i<n;i++) add(in(),in(),in());solve(1,n);printf("%d\n",ans);ans=0;}
}