Tang-Dreamoon's Blog

poj 1741 Tree

发表于 | 分类于 ， ，

点分治入门（一）

　　题目链接：poj 1741

　　题意：求树上距离小于等于 K 的点对有多少个。

　　题解：首先求出几个数组，我们假设每一个点在树中的深度为 W[i] ，以及每个点在 Root 的哪一个子节点的子树中，记为 Bi。把树中的点都取出来，按照 W[i] 升序排序。只需要用两个指针 X、Y 一个从前一个从后开始扫描统计答案即可，对于左指针 X 找到最靠右的右指针 Y 满足 W[X]+W[Y]≤K ，设 DP[i] 表示在左右指针之间的满足 B[X]=i 的点 X 的个数，这时 Y-X-DP[B[X]] 就是要求的答案。

　　我思故我在：点分治的重点在于对每一层状态的处理。这个的题目给我的教训是如何做到在不用 Memset 的情况下对于状态数组的还原和改变。还有就是我一开始没有想到如何正确的维护 DP 数组，还愚蠢的用了前缀和来计算，导致空间开不下而爆炸。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
int n,m;
long long k;
int mina,head;
int tot;
long long  ans=0;
struct table{
	int to,vl;
};
struct node{
	long long  val,belong;
}map[10010];
long long  w[10010];
int fa[10010];
int dp[100100];
int size[10010];
bool biao[10010];
vector<table> ve[10010];
void dfs(int x)
{
	size[x]=0;
	for(int i=0;i<ve[x].size();i++)
	{
		table y=ve[x][i];
		if(y.to!=fa[x]&&!biao[y.to])
		{
			fa[y.to]=x;
			dfs(y.to);
			size[x]+=size[y.to];
		}
	}
	size[x]++;
}
void getroot(int x)
{
	int maxa=-1;
	for(int i=0;i<ve[x].size();i++)
	{
		table y=ve[x][i];
		if(y.to!=fa[x]&&!biao[y.to])
		{
			getroot(y.to);
			maxa=max(maxa,size[y.to]);
		}
	}
	maxa=max(maxa,m-size[x]);
	if(maxa<mina)
		mina=maxa,head=x;
}
void suan(int x,int now)
{
	for(int i=0;i<ve[x].size();i++)
	{
		table y=ve[x][i];
		if(y.to!=fa[x]&&!biao[y.to])
		{
			fa[y.to]=x,map[++tot].val=w[y.to]=w[x]+y.vl,map[tot].belong=now;
			suan(y.to,now);
		}
	}
}
bool cmp(node a,node b)
{
	return a.val<b.val;
}
void fz(int x)
{
	fa[x]=x;
	dfs(x);
	m=size[x],mina=2147483647;
	getroot(x);
	int fuck=head;
	biao[fuck]=1;
	tot=0;
	map[++tot].val=w[fuck]=0,map[tot].belong=0,dp[0]=0;
	for(int i=0;i<ve[fuck].size();i++)
	{
		table y=ve[fuck][i];
		if(!biao[y.to])
		{
			dp[i+1]=0;
			fa[y.to]=fuck,map[++tot].val=w[y.to]=y.vl,map[tot].belong=i+1,suan(y.to,i+1);
		}
	}
	sort(map+1,map+1+tot,cmp);
	for(int i=1;i<=tot;i++)
		dp[map[i].belong]++;
	int l=1,r=tot;
	while(l<r)
	{
		dp[map[l].belong]--;
		while(map[l].val+map[r].val>k) dp[map[r].belong]--,r--;
		if(r<=l) break;
		ans+=r-l-dp[map[l].belong];
		l++;
	}
	for(int i=0;i<ve[fuck].size();i++)
	{
		table y=ve[fuck][i];
		if(!biao[y.to])
			fz(y.to);
	}
}
int main()
{
	while(scanf("%d%lld",&n,&k)!=EOF&&n!=0)
	{
		for(int i=1;i<n;i++)
		{
			int x,y,z;
			scanf("%d%d%d",&x,&y,&z);
			ve[x].push_back((table){y,z});
			ve[y].push_back((table){x,z});
		}
		m=n;
		fz(1);
		printf("%lld\n",ans);
		ans=0;
		memset(biao,0,sizeof(biao));
		for(int i=1;i<=n;i++)
			ve[i].clear();
	}
	return 0;
}