题解 P3806 【【模板】点分治1】
officeyutong
2018-01-27 22:44:04
嗯..上语文课自己YY出来的点分治,完全不知道其他dalao们是怎么写的
我的思路大概是三遍DFS 第一遍找出树的重心
第二遍以重心为根 算出所有子树的大小 所有点到根节点的距离 以及整棵树的DFS序
第三遍就是算法的核心 递归计算结果 具体见代码注释
```cpp
// luogu-judger-enable-o2
/*
* To change this license header, choose License Headers in Project Properties.
* To change this template file, choose Tools | Templates
* and open the template in the editor.
*/
/*
* File: main.cpp
* Author: Ytong
*
* Created on 2018年1月26日, 下午12:56
*/
#include <cstdlib>
#include <vector>
#include <iostream>
#include <cstring>
#include <algorithm>
using std::vector;
using std::cin;
using std::cout;
using std::endl;
using std::vector;
using std::max;
using std::min;
using int_t = long int;
const int_t LARGE = 10000;
//统计[start,end]内满足*a+*b==k的数对数
int_t countN(int_t* start, int_t * end, int_t k) {
int_t result = 0;
while (start < end) {
if (*start + *end == k) {
result++;
int_t * temp = end;
while (*(temp - 1) == *temp && start < temp) {
temp--;
result++;
}
start++;
} else if (*start + *end < k) {
start++;
} else {
end--;
}
}
return result;
}
struct Edge {
int_t to;
int_t weight;
Edge(int_t to, int_t weight) :
to(to), weight(weight) {
}
};
vector<Edge> graph[LARGE + 1];
int_t size[LARGE + 1];
int_t dfsSeq[LARGE + 1];
int_t dis[LARGE + 1];
int_t n, m;
int_t root;
int_t temp[LARGE + 1];
//第一个DFS 找重心
int_t massCenter = -1;
int_t massCenterSize = 0x7fffffff;
int_t DFS1(int_t vertex, int_t from = -1) {
int_t result = 0;
int_t _size = 1;
for (Edge& x : graph[vertex]) {
if (x.to != from) {
int_t _temp = DFS1(x.to, vertex);
result = max(result, _temp);
_size += _temp;
}
}
result = max(result, n - _size);
if (result < massCenterSize) {
massCenterSize = result;
massCenter = vertex;
}
return _size;
}
//基于新的树根 求出所有子树的大小 所有点到根节点的权值 所有点的DFS序
//返回子树的大小
int_t DFS2(int_t vertex, int_t from = -1, int_t dis_ = 0) {
dfsSeq[++dfsSeq[0]] = vertex;
int_t currSize = 1;
dis[vertex] = dis_;
for (Edge& edge : graph[vertex]) {
if (edge.to != from) {
int_t _size = DFS2(edge.to, vertex, dis_ + edge.weight);
currSize += _size;
}
}
size[vertex] = currSize;
return currSize;
}
//算法核心
//当前的节点vertex 对应dfs序中[left,right]
//统计距离为K的点对个数
int_t DFS3(int_t vertex, int_t* left, int_t* right, int_t K, int_t from = -1) {
//以树根为一个端点的符合要求的点对数
int_t cnt1 = 0;
//两端都在一棵子树内的点对个数
//统计出整颗子树内符合要求的点对数后 减去cnt2 结果就是经过子树树根的符合要求的点对数
int_t cnt2 = 0;
//递归所得到的结果和
int_t cnt3 = 0;
int_t * pos = left + 1;
for (Edge& edge : graph[vertex]) {
if (edge.to != from) {
//1.递归处理
cnt3 += DFS3(edge.to, pos, pos + size[edge.to] - 1, K, vertex);
//2.统计当前两端都在当前子树内的点对数
//以及一端为树根的点对数
for (int_t *x = pos; x <= pos + size[edge.to] - 1; x++) {
int_t i = x - pos + 1;
temp[i] = dis[*x] - dis[vertex];
if (temp[i] == K) {
// cout << "子树" << vertex << " 以树根为一端点的点对 " << *x << " 统计子树 " << edge.to << "时计入" << endl;
cnt1++;
}
}
std::sort(&temp[1], &temp[size[edge.to] + 1]);
cnt2 += countN(&temp[1], &temp[size[edge.to]], K);
pos += size[edge.to];
}
}
for (int_t i = 1; i <= size[vertex] - 1; i++) {
temp[i] = dis[*(left + i)] - dis[vertex];
}
std::sort(&temp[1], &temp[size[vertex]]);
// cout << "子树" << vertex << " 统计结束 " << " 以树根为一端的点对数:" << cnt1 << " 递归结果:" << cnt3 << " 两端都在一个子树内的点对数 " << cnt2 << " 子树内所有符合要求的点对数 " << countN(&temp[1], &temp[size[vertex] - 1], K) << endl;
// cout << "子树" << vertex << " 的总序列为";
// for (int_t i = 1; i <= size[vertex] - 1; i++) cout << temp[i] << " ";
// cout << endl;
//结果=递归得到的结果+以树根为一个端点的符合要求的点对数+整颗子树内符合要求的点对数-完全在一棵子树内的符合要求的点对数
return cnt1 + cnt3 + countN(&temp[1], &temp[size[vertex] - 1], K) - cnt2;
}
int main(int argc, char** argv) {
cin >> n>>m;
for (int_t i = 1; i <= n - 1; i++) {
int_t from;
int_t to;
int_t weight;
cin >> from >> to>>weight;
graph[from].push_back(Edge(to, weight));
graph[to].push_back(Edge(from, weight));
}
DFS1(rand() % n + 1);
root = massCenter;
DFS2(root);
for (int_t i = 1; i <= m; i++) {
int_t x;
cin>>x;
if (DFS3(root, &dfsSeq[1], &dfsSeq[n], x)) {
cout << "AYE" << endl;
} else {
cout << "NAY" << endl;
}
}
return 0;
}
```
算法的速度还可以，开-O2的情况下最慢的点164ms