BZOJ 2599 IOI2011 Race 樹的點分治
題目大意：給出N(1 <= N <= 200000)個結點的樹，求長度等於K(1 <= K <= 1000000)的路徑的最小邊數
樹的點分治，統計方法同POJ1741，不過比較討厭的一點是最小值不支持區間減法，所以直接把所有路經長=k的方案都計入ans，然後就可以相減了，最後從左到右掃一遍即可~
寫的好慢。。。基本就是卡時過的 RANK1那家伙到底寫了啥。。。
#include
#include
#include
#include
#define M 200200
using namespace std;
struct abcd{
int to,f,next;
bool ban;
}table[M<<1];
int head[M],tot=1;
int n,k;
int siz[M],fa[M],ans[M],dis[M],dpt[M];
pairstack[M];int top;
void Find_Centre_Of_Gravity(int x,int size,int &cg)
{
int i;
bool flag=1;
siz[x]=1;
for(i=head[x];i;i=table[i].next)
{
if(table[i].to==fa[x]||table[i].ban)
continue;
fa[table[i].to]=x;
Find_Centre_Of_Gravity(table[i].to,size,cg);
siz[x]+=siz[table[i].to];
if(siz[table[i].to]>size>>1)
flag=0;
}
if(size-siz[x]>size>>1)
flag=0;
if(flag)
cg=x;
}
void DFS1(int x,int d,int deep,int from)
{
int i;
dis[x]=d;
dpt[x]=deep;
fa[x]=from;
for(i=head[x];i;i=table[i].next)
{
if(table[i].to==fa[x]||table[i].ban)
continue;
DFS1(table[i].to,d+table[i].f,deep+1,x);
}
}
void DFS2(int x)
{
int i;
stack[++top]=make_pair(dis[x],dpt[x]);
for(i=head[x];i;i=table[i].next)
{
if(table[i].to==fa[x]||table[i].ban)
continue;
DFS2(table[i].to);
}
}
void Calculate(int x,int flag)
{
int i,j,l;
top=0,DFS2(x);
sort(stack+1,stack+top+1);
for(j=top,i=1;i<=top;i++)
{
for(;j&&stack[i].first+stack[j].first>k;j--);
for(l=j;k&&stack[i].first+stack[l].first==k;l--)
ans[stack[i].second+stack[l].second]+=flag;
}
}
void Tree_Divide_And_Conquer(int root,int size)
{
int i,cg;
Find_Centre_Of_Gravity(root,size,cg);
if(fa[cg])
siz[fa[cg]]=size-siz[cg];
DFS1(cg,0,0,0);
Calculate(cg,1);
for(i=head[cg];i;i=table[i].next)
if(!table[i].ban)
{
table[i].ban=table[i^1].ban=1;
Calculate(table[i].to,-1);
Tree_Divide_And_Conquer(table[i].to,siz[table[i].to]);
}
}
void Add(int x,int y,int z)
{
table[++tot].to=y;
table[tot].f=z;
table[tot].next=head[x];
head[x]=tot;
}
int main()
{
int i,x,y,z;
cin>>n>>k;
for(i=1;i
