首页 > 代码库 > POJ1741Tree [点分治]【学习笔记】

POJ1741Tree [点分治]【学习笔记】

2024-08-31 10:57:08   216人阅读

Tree
Time Limit: 1000MS Memory Limit: 30000K
Total Submissions: 20098 Accepted: 6608

Description

Give a tree with n vertices,each edge has a length(positive integer less than 1001). 
Define dist(u,v)=The min distance between node u and v. 
Give an integer k,for every pair (u,v) of vertices is called valid if and only if dist(u,v) not exceed k. 
Write a program that will count how many pairs which are valid for a given tree. 

Input

The input contains several test cases. The first line of each test case contains two integers n, k. (n<=10000) The following n-1 lines each contains three integers u,v,l, which means there is an edge between node u and v of length l. 
The last test case is followed by two zeros. 

Output

For each test case output the answer on a single line.
题意：给一颗带权树，求树上长度不超过L的路径条数
首先有一个有树高限制时的树形DP做法..........
 

对于一条树路径 只有经过或不经过一个点的情况

考虑经过一个点的路径，可以由其他点到它的两条路径拼出来

对于不经过的情况 把一棵树按这个点拆成好几棵分治
 
每次对于当前子树选择树的重心，最多递归logn次，而每层最多只有n个点(每层的所有子树组成整棵树)，复杂度O(logn*处理每层的复杂度)
 
过程：
1.求重心
2.处理经过当前点的路径
3.对子树分治
 
每次分治的各个子树是互不影响的，vis[i]表示i这个点已经分治过了
 
对于本题，处理经过点u的路径时，先dfs子树中所有点对深度，排序两个指针往里扫计算<=L的，在减去在同一颗子树里的(同样计算)
总复杂度O(nlog^2n)
 
 
#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>using namespace std;const int N=10005,INF=1e9+5;inline int read(){    char c=getchar();int x=0,f=1;    while(c<‘0‘||c>‘9‘){if(c==‘-‘)f=-1;c=getchar();}    while(c>=‘0‘&&c<=‘9‘){x=x*10+c-‘0‘;c=getchar();}    return x*f;}int n,L,u,v,w;struct edge{    int v,w,ne;}e[N<<1];int h[N],cnt;inline void ins(int u,int v,int w){    cnt++;    e[cnt].v=v;e[cnt].w=w;e[cnt].ne=h[u];h[u]=cnt;    cnt++;    e[cnt].v=u;e[cnt].w=w;e[cnt].ne=h[v];h[v]=cnt;}int size[N],d[N],vis[N],root,sum;void dfsRoot(int u,int fa){    size[u]=1;d[u]=0;    for(int i=h[u];i;i=e[i].ne){        int v=e[i].v;        if(vis[v]||v==fa) continue;        dfsRoot(v,u);        size[u]+=size[v];        d[u]=max(d[u],size[v]);    }    d[u]=max(d[u],sum-size[u]);    if(d[u]<d[root]) root=u;}int deep[N],a[N];void dfsDeep(int u,int fa){    a[++a[0]]=deep[u];    for(int i=h[u];i;i=e[i].ne){        int v=e[i].v;        if(vis[v]||v==fa) continue;        deep[v]=deep[u]+e[i].w;        dfsDeep(v,u);    }}int cal(int u,int now){    deep[u]=now;a[0]=0;    dfsDeep(u,0);    sort(a+1,a+1+a[0]);    int l=1,r=a[0],ans=0;    while(l<r){        if(a[l]+a[r]<=L) ans+=r-l,l++;        else r--;    }    return ans;}int ans;void dfsSol(int u){//printf("dfs %d\n",u);    vis[u]=1;    ans+=cal(u,0);    for(int i=h[u];i;i=e[i].ne){        int v=e[i].v;        if(vis[v]) continue;        ans-=cal(v,e[i].w);        sum=size[v];        root=0;dfsRoot(v,0);        dfsSol(root);    }}int main(){    //freopen("in.txt","r",stdin);    while(true){        n=read();L=read();if(n==0) break;        cnt=0;memset(h,0,sizeof(h));        memset(vis,0,sizeof(vis));        ans=0;        for(int i=1;i<=n-1;i++) u=read(),v=read(),w=read(),ins(u,v,w);        sum=n;        root=0;d[0]=INF;        dfsRoot(1,0);        dfsSol(root);        printf("%d\n",ans);    }}

 

 
 
 
 
 

POJ1741Tree [点分治]【学习笔记】


联系
我们