点分治第一题
这题我们考虑点分治
首先我们需要找到树的重心
然后做一遍
然后分成左右两块继续做，每一块重复上面的操作
具体的，我们每次计算每个点到重心的距离
然后放到一个数组里，再将距离和小于k的算进去
但是有可能重复统计了子树里面的数值
所以点分治的时候再减一下就好了
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
int n,k,h[10005],en,mx[10005],siz[10005],ans,root,val,vis[10005],temp[10005],cnt;
struct Edge{
int b,v,next;
}e[20005];
void AddEdge(int sa,int sb,int sc){
e[++en].b=sb;
e[en].v=sc;
e[en].next=h[sa];
h[sa]=en;
}
void DfsSiz(int u,int fa){
siz[u]=1;
mx[u]=0;
for(int i=h[u];i;i=e[i].next){
int v=e[i].b;
if(v!=fa && !vis[v]){
DfsSiz(v,u);
siz[u]+=siz[v];
mx[u]=max(mx[u],siz[v]);
}
}
}
void DfsRoot(int point,int u,int fa){
mx[u]=max(mx[u],siz[point]-siz[u]);
if(val>mx[u]){val=mx[u];root=u;}
for(int i=h[u];i;i=e[i].next){
int v=e[i].b;
if(v!=fa && !vis[v])DfsRoot(point,v,u);
}
}
void GetDist(int u,int fa,int val){
temp[++cnt]=val;
for(int i=h[u];i;i=e[i].next){
int v=e[i].b;
if(v!=fa && !vis[v])GetDist(v,u,val+e[i].v);
}
}
int Cal(int u,int val){
cnt=0;
int now=0;
GetDist(u,u,val);
sort(temp+1,temp+cnt+1);
int i=1,j=cnt;
while(i<j){
while(temp[i]+temp[j]>k && i<j)j--;
now+=j-i;
i++;
}
return now;
}
void Dfs(int u){
val=2100000000;
DfsSiz(u,u);
DfsRoot(u,u,0);
ans+=Cal(root,0);
vis[root]=1;
for(int i=h[root];i;i=e[i].next){
int v=e[i].b;
if(!vis[v]){
ans-=Cal(v,e[i].v);
Dfs(v);
}
}
}
int main(){
freopen("1741.in","r",stdin);
freopen("1741.out","w",stdout);
while(scanf("%d %d",&n,&k),n|k){
memset(h,0,sizeof(h));
memset(vis,0,sizeof(vis));
ans=en=0;
for(int i=1;i<n;i++){
int sa,sb,sc;
scanf("%d %d %d",&sa,&sb,&sc);
AddEdge(sa,sb,sc);
AddEdge(sb,sa,sc);
}
Dfs(1);
printf("%d\n",ans);
}
return 0;
}
Sep 08, 2022 10:05:58 PM
The AP Intermediate students can download the Economics question bank with solved study material with practice questions in chapter wise to every TM, EM, UM student, and the economics subject paper-1 AP 2nd Inter Economics Model Paper and paper-2 important questions with suggestions are available through AP Jr and Sr inter Economics Model Paper 2023 Pdf with guess paper. The AP Intermediate students can download the Economics question bank with solved study material with practice questions in chapter wise to every TM, EM, UM student