tree

初学树分治的学习笔记。

题目

分治本质上都是一样的，就是要把原问题分割成几个规模更小的问题分别求解然后再合并上去。而由于树它本身具有很强的递归特性（笼统的说就是树的部分还是树），于是就使得树上分治成为可能。

树分治一般遵循以下步骤：

第一步，把树中所有节点全部找出来，然后把它们近乎于暴力地统计一遍答案（此步骤一般是 \(O(N)/O(NlogN)\)），而且此步骤只统计所有经过根节点的路径；第二步就是找到当前这棵树的重心（这样可以使得分治下去的问题规模得到保障从而保证复杂度），然后递归处理即可。整体复杂度是\(O(NlogN)\)左右。

按照这个思路就可以写这道题了。

#include
#include
#include
//#define zczc
#define ll long long
using namespace std;
const int N=40010;
const int maxn=1e9;
using namespace std;
inline void read(int &wh){
	wh=0;int f=1;char w=getchar();
	while(w<'0'||w>'9'){if(w=='-')f=-1;w=getchar();}
	while(w<='9'&&w>='0'){wh=wh*10+w-'0';w=getchar();}
	wh*=f;return;
}
inline int max(int s1,int s2){
	return s1