# 【BZOJ-1468】Tree 树分治

## 1468: Tree

Time Limit: 10 Sec  Memory Limit: 64 MB
Submit: 1025  Solved: 534
[Submit][Status][Discuss]

## Input

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

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

5

LTC男人八题系列

## Code

```#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int read()
{
int x=0,f=1; char ch=getchar();
while (ch<‘0‘ || ch>‘9‘) {if (ch==‘-‘) f=-1; ch=getchar();}
while (ch>=‘0‘ && ch<=‘9‘) {x=x*10+ch-‘0‘; ch=getchar();}
return x*f;
}
#define maxn 80010
int n,root,siz,ans,stack[maxn],top,K;
struct Edgenode{int to,next,val;}edge[maxn<<1];
int head[maxn],cnt=1;
void add(int u,int v,int w)
{cnt++; edge[cnt].val=w; edge[cnt].to=v; edge[cnt].next=head[u]; head[u]=cnt;}
void insert(int u,int v,int w)
{add(u,v,w);add(v,u,w);}
int gcd(int a,int b)
{if (b==0) return a; return gcd(b,a%b);}
int size[maxn],maxx[maxn],val[maxn]; bool visit[maxn];
void DFSroot(int now,int last)
{
size[now]=1; maxx[now]=0;
for (int i=head[now]; i; i=edge[i].next)
if (edge[i].to!=last && !visit[edge[i].to])
{
DFSroot(edge[i].to,now);
size[now]+=size[edge[i].to];
maxx[now]=max(maxx[now],size[edge[i].to]);
}
maxx[now]=max(maxx[now],siz-size[now]);
if (maxx[now]<maxx[root]) root=now;
}
void DFSval(int now,int last)
{
stack[++top]=val[now];
for (int i=head[now]; i; i=edge[i].next)
if (edge[i].to!=last && !visit[edge[i].to])
{
val[edge[i].to]=val[now]+edge[i].val;
DFSval(edge[i].to,now);
}
}
int Getans(int now,int va)
{
val[now]=va; top=0; DFSval(now,0);
sort(stack+1,stack+top+1);
int re=0,l=1,r=top;
while (l<r) if (stack[l]+stack[r]<=K) re+=r-l,l++; else r--;
return re;
}
void work(int now)
{
ans+=Getans(now,0);
visit[now]=1;
for (int i=head[now]; i; i=edge[i].next)
if (!visit[edge[i].to])
{
ans-=Getans(edge[i].to,edge[i].val);
root=0; siz=size[edge[i].to];
DFSroot(edge[i].to,0); work(root);
}
}
int main()
{
n=read();
for (int u,v,w,i=1; i<=n-1; i++)
u=read(),v=read(),w=read(),insert(u,v,w);
K=read();
maxx[0]=siz=n;
DFSroot(1,0);
work(root);
printf("%d\n",ans);
return 0;
}```

## bzoj 1468 Tree(点分治模板)

1468: Tree Time Limit: 10 Sec  Memory Limit: 64 MBSubmit: 1527  Solved: 818[Submit][Status][Discuss] Description 给你一棵TREE,以及这棵树上边的距离.问有多少对点它们两者间的距离小于等于K Input N(n<=40000) 接下来n-1行边描述管道,按照题目中写的输入 接下来是k Output 一行,有多少对点之间的距离小于等于k Sample Input 7 1 6 13 6

## poj 1744 tree 树分治

Tree Time Limit: 1000MS   Memory Limit: 30000K       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 ve