【树的分治统计点对距离

时间:2022-02-12 00:53:59

虽然是看别人做的,但是有点不明白他那个标记数组vis,因为他标记的是反向边,而我习惯标记点,因此搞了很久,终于让我想明白了,如果想要标记点的话,因为是双向邻接表,只需要标记分治出来的根节点就行了,然后一层层分治下去,好好体会http://hi.baidu.com/yy17yy/blog/item/865dee006f8663147aec2cee.html

#define N  10010

struct edge{
int v;
int next;
int w;
}e[N*2];
int head[N];
bool vis[N];
int ecnt;
int k;
int ans;
int q1[N],q2[N];
int e1,e2;
void init(){
memset(head,-1,sizeof(head));
memset(vis,0,sizeof(vis));
ecnt=0;
}
void add(int u,int v,int w){
e[ecnt].v = v;
e[ecnt].w = w;
e[ecnt].next = head[u];
head[u] = ecnt++;

e[ecnt].v = u;
e[ecnt].w = w;
e[ecnt].next = head[v];
head[v] = ecnt++;
}
void cal(int u,int fa,int w){
int i,j;
q1[++e1] = w;
q2[++e2] = w;
for(i=head[u];i!=-1;i=e[i].next){
int v = e[i].v;
if(v==fa || vis[v])continue;
cal(v,u,e[i].w+w);
}
}
int sum(int *q,int t){
int i,j;
sort(q+1,q+t+1);
int tot=0;
for(i=1,j=t;;i++){
while(q[i]+q[j]>k){
j--;
}
if(j<=i)break;
tot += j-i;
}
return tot;
}
int tot;
int dp[N];
void DP(int u,int fa){
int i,j;
tot++;
dp[u] = 1;
for(i=head[u];i!=-1;i=e[i].next){
int v = e[i].v;
if(v==fa || vis[v])continue;
DP(v,u);
dp[u]+=dp[v];
}
}
int minm,tag;
void dfs(int u,int fa){
int tmp = tot - dp[u];
int i;
for(i=head[u];i!=-1;i=e[i].next){
int v = e[i].v;
if(v==fa || vis[v])continue;
tmp = max(tmp,dp[v]);
dfs(v,u);
}
if(tmp<minm){
minm = tmp;
tag = u;
}
}
int find(int u){
tot = 0;
DP(u,-1);//树形dp,统计以u为根结点的子树的结点数
if(tot==1)return -1;
minm = 1<<30;
dfs(u,-1);
return tag;
}

void work(int u){
u = find(u);//找最优分治点,要求将其删去后,结点最多的树的结点个数最小
if(u == -1)return ;
int i,j;
e1 = 0;
q1[++e1] = 0;
for(i=head[u];i!=-1;i=e[i].next){
int v = e[i].v;
int w = e[i].w;
if(vis[v])continue;
e2 = 0;
cal(v,u,w);//统计子树每点到子树根的距离
ans -= sum(q2,e2);//sum计算q中<=k的结点对数
}
ans += sum(q1,e1);
vis[u] = 1;//因为用双向邻接表记录,所以只需要标记分治的根结点!!!
for(i=head[u];i!=-1;i=e[i].next){
int v = e[i].v;
if(vis[v])continue;
//vis[v] = 1;
work(v);
}
}

int main(){
int n;
while(scanf("%d%d",&n,&k) && (n+k)){
int i,j;
int u,v,w;
init();
for(i=1;i<n;i++){
scanf("%d%d%d",&u,&v,&w);
add(u,v,w);
}
ans=0;
work(1);
printf("%d\n",ans);
}
return 0;
}