首页 > 代码库 > [bzoj 1468] Tree

[bzoj 1468] Tree

2024-09-26 18:12:39   214人阅读

传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=1468

Tree

Time Limit: 10 Sec  Memory Limit: 64 MB
Submit: 1517  Solved: 812
[Submit][Status][Discuss]

Description

给你一棵TREE,以及这棵树上边的距离.问有多少对点它们两者间的距离小于等于K

Input

N（n<=40000） 接下来n-1行边描述管道，按照题目中写的输入 接下来是k

Output

一行，有多少对点之间的距离小于等于k

Sample Input

7
1 6 13
6 3 9
3 5 7
4 1 3
2 4 20
4 7 2
10

Sample Output

5

点分治裸题，和poj上的不一样，不一样！！！

  1 #include<cstdio>  2 #include<cctype>  3 #include<cstring>  4 #include<algorithm>  5 #define gc() getchar()  6 #define max(a,b) ((a)>(b)?(a):(b))  7 using namespace std;  8 int read()  9 { 10     int rt=0,fl=1;char ch=gc(); 11     while(!isdigit(ch)){if(ch==‘-‘)fl=-1;ch=gc();} 12     while(isdigit(ch)){rt=rt*10+ch-‘0‘;ch=gc();} 13     return rt*fl; 14 } 15   16 const int MAXN = 100005; 17   18 int h[MAXN],nx[MAXN<<1],to[MAXN<<1],val[MAXN<<1],cnt; 19 int son[MAXN],f[MAXN],d[MAXN],deep[MAXN],root,sum,n,k,ans; 20 bool vis[MAXN]; 21   22 void add_edge(int _u,int _v,int _c) 23 { 24     to[++cnt]=_v; 25     nx[cnt]=h[_u]; 26     h[_u]=cnt; 27     val[cnt]=_c; 28 } 29   30 void link(int _u,int _v,int _c) 31 { 32     add_edge(_u,_v,_c); 33     add_edge(_v,_u,_c); 34 } 35   36 void clear() 37 { 38     memset(h,0,sizeof(h)); 39     memset(vis,0,sizeof(vis)); 40     cnt=0; 41     ans = root = 0; 42 } 43   44 void getRoot(int rt,int fa) 45 { 46     son[rt]=1; 47     f[rt]=0; 48     for(int i=h[rt];i;i=nx[i]) 49     { 50         if(to[i]==fa || vis[to[i]]==1)continue; 51         getRoot(to[i],rt); 52         son[rt] += son[to[i]]; 53         f[rt] = max(f[rt],son[to[i]]); 54     } 55     f[rt] = max(f[rt],sum - son[rt]); 56     if(f[rt] < f[root]) root = rt; 57 } 58   59 void getDeep(int rt,int fa) 60 { 61     deep[++deep[0]] = d[rt]; 62     for(int i=h[rt];i;i=nx[i]) 63     { 64         if(to[i]==fa || vis[to[i]]==1)continue; 65         d[to[i]] = d[rt] + val[i]; 66         getDeep(to[i],rt); 67     } 68 } 69   70 int cal(int x,int now) 71 { 72     d[x] = now; 73     deep[0] = 0; 74     getDeep(x,0); 75     sort(deep+1,deep+deep[0]+1); 76     int t = 0,l,r; 77     for(l=1,r=deep[0];l<r;) 78     { 79         if(deep[l] + deep[r] <= k) 80         { 81             t+=r-l; 82             l++; 83         } 84         else r--; 85     } 86     return t; 87 } 88 void work(int rt) 89 { 90     ans += cal(rt,0); 91     vis[rt] = 1; 92     for(int i=h[rt];i;i=nx[i]) 93     { 94         if(vis[to[i]]==1) continue; 95         ans -= cal(to[i],val[i]); 96         sum = son[to[i]]; 97         root = 0; 98         getRoot(to[i],root); 99         work(root);100     }101 }102 int main()103 {104     n=read();105     for(int i=1;i<n;i++)106     {107         int a,b,c;108         a=read();109         b=read();110         c=read();111         link(a,b,c);112         }113     k=read();114         sum = n;115         f[0] = 0x3f3f3f3f;116         getRoot(1,0);117         work(root);118         printf("%d\n",ans);119     return 0;120 }

 

[bzoj 1468] Tree


联系
我们