首页 > 代码库 > poj 1741

poj 1741

2024-08-16 10:25:09   224人阅读

题意：求一棵树上任意两点之间距离小于k的点对有多少个

分析：树分治的练手题，找到重心以后，我们要求所有经过中心的点，如何求这样的点呢，显然，所有的路径可以分为过重心，不过中心，终点是重心，所有点到达重心的距离很好求，可以很容易的求出，这些边由两部分组成，来自不同的儿子和来自相同的儿子，只要减去来自相同的儿子的数量就是过重心的数量

#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<vector>using namespace std;const int maxn=2e4+5;typedef long long ll;typedef  unsigned long long ull;int vis[maxn],n,k,num,d[maxn],_min,tsize[maxn],tssize[maxn],root;int head[maxn],next[maxn],edge[maxn],val[maxn],tot;ll ans;void init(){    memset(vis,0,sizeof(vis));    tot=ans=0;    memset(head,-1,sizeof(head));}void addedge(int u,int v,int w){    edge[tot]=v;    val[tot]=w;    next[tot]=head[u];    head[u]=tot++;}//获取子树大小和子树的最大值void getsize(int u,int f){    tsize[u]=1;tssize[u]=0;    for(int i=head[u];i!=-1;i=next[i]){        int v=edge[i];        if(v==f||vis[v])continue;        getsize(v,u);        tsize[u]+=tsize[v];        tssize[u]=max(tssize[u],tsize[v]);    }}//重心void getroot(int r,int u,int f){    tssize[u]=max(tssize[u],tsize[r]-tsize[u]);    if(tssize[u]<_min)_min=tssize[u],root=u;    for(int i=head[u];i!=-1;i=next[i]){        int v=edge[i];        if(v==f||vis[v])continue;        getroot(r,v,u);    }}//求所有点到u的距离void getdis(int u,int dcnt,int f){    d[num++]=dcnt;    for(int i=head[u];i!=-1;i=next[i]){        int v=edge[i];int w=val[i];        if(v==f||vis[v])continue;getdis(v,dcnt+w,u);    }}int cal(int u,int dcnt){    num=0;int ret=0;    getdis(u,dcnt,-1);    int i=0,j=num-1;    sort(d,d+num);    //for(int i=0;i<num;i++)cout<<d[i]<<" ";cout<<endl;    while(i<j){        while(d[i]+d[j]>k&&i<j)j--;        ret+=j-i;        i++;    }    //cout<<ret<<endl;    return ret;}void dfs(int u){    _min=n;    getsize(u,-1);    getroot(u,u,-1);//cout<<root<<endl;    ans+=cal(root,0);    //cout<<root<<"  "<<ans<<endl;    vis[root]=1;    int qqq=root;    for(int i=head[qqq];i!=-1;i=next[i]){        int v=edge[i],w=val[i];        if(vis[v])continue;        ans-=cal(v,w);        dfs(v);    }    //cout<<root<<"  "<<ans<<endl;}int main(){	//freopen("in","r",stdin);	ios::sync_with_stdio(false);    while(cin>>n>>k&&n+k){        init();        for(int i=0;i<n-1;i++){            int u,v,w;cin>>u>>v>>w;            addedge(u,v,w);addedge(v,u,w);        }        dfs(1);        cout<<ans<<endl;    }	return 0;}

 

poj 1741


联系
我们