一句话点分治：每次找到树的重心，暴力或者不暴力处理以这个重心为分界点的 各个子树 之间 产生的贡献，然后删除这个点，产生很多树，对每棵子树重复上述操作。。。
有点像dsu on tree，都是通过均摊来实现nlogn
P3806
提供一种离线处理询问的做法：
点分的过程中在对root的单独处理时，每处理一个子树，就用由root其他子树构成的桶去离线处理询问是否存在。最后处理完root的所有子树相互之间产生的贡献后，把桶清空。
void cal(int from)
{
tmp.clear();
int last, now;
for (int i = head[from]; ~i; i = e[i].next)
{
int to = e[i].to, cost = e[i].cost;
if (vis[to])continue;
last = tmp.size();
//getdis是把子树中得到的路径长度加入tmp中，并得到tmp中的起点last和终点now（暂时不clear，留着最后清空桶）
getdis(to, from, cost);
now = tmp.size() - 1;
//makeans
for (int i = 1; i <= m; i++)
{
int ans = q[i];//当前询问的值
if (ok[i])continue;//已存在，跳过
for (int j = last; j <= now; j++)//遍历当前的子树可以得到的路径长度
if (ans >= tmp[j] && cnt[ans - tmp[j]])//桶中有这样的值
{
ok[i] = 1;//存在
break;
}
}
//insert_cnt
for (int i = last; i <= now; i++)
if (tmp[i] <= 10000000)
cnt[tmp[i]] = 1;
}
//clear_cnt
for (auto i : tmp)
if (i <= 10000000)
cnt[i] = 0;
}
求重心：
void find(int from, int fa)//找重心
{
siz[from] = 1, mx[from] = 0;
for (int i = head[from]; ~i; i = e[i].next)
{
int to = e[i].to;
if (to == fa || vis[to])continue;
find(to, from);
siz[from] += siz[to];
mx[from] = max(mx[from], siz[to]);
}
mx[from] = max(mx[from], tot - siz[from]);
if (mx[from] < mx[root])
root = from;
}
点分：
void divid(int from)
{
vis[from] = 1;
cal(from);
for (int i = head[from]; ~i; i = e[i].next)
{
int to = e[i].to;
if (vis[to])continue;
tot = siz[to];
root = 0;
find(to, from);
divid(root);
}
}
最终代码：
#include<bits/stdc++.h>
#define ll long long
#define fastio ios::sync_with_stdio(false),cin.tie(NULL),cout.tie(NULL)
using namespace std;
const ll mod = 998244353;
const int maxn = 1e5 + 5;
const int inf = 1e9 + 7;
const ll lnf = 1e18;
struct edge {
int to, cost, next;
}e[maxn << 1];
int edge_cnt = 0, head[maxn];
void add(int from, int to,int cost)
{
e[++edge_cnt] = { to,cost, head[from] };
head[from] = edge_cnt;
}
int siz[maxn], tot, mx[maxn];
int root = 0;
bool vis[maxn];
int n, m;
void find(int from, int fa)//找重心
{
siz[from] = 1, mx[from] = 0;
for (int i = head[from]; ~i; i = e[i].next)
{
int to = e[i].to;
if (to == fa || vis[to])continue;
find(to, from);
siz[from] += siz[to];
mx[from] = max(mx[from], siz[to]);
}
mx[from] = max(mx[from], tot - siz[from]);
if (mx[from] < mx[root])
root = from;
}
int q[105], ok[105];
bool cnt[10000005];
vector<int>tmp;
void getdis(int from, int fa, int res)
{
tmp.push_back(res);
for (int i = head[from]; ~i; i = e[i].next)
{
int to = e[i].to, cost = e[i].cost;
if (vis[to] || to == fa)continue;
getdis(to, from, res + cost);
}
}
void cal(int from)
{
tmp.clear();
int last, now;
for (int i = head[from]; ~i; i = e[i].next)
{
int to = e[i].to, cost = e[i].cost;
if (vis[to])continue;
last = tmp.size();
getdis(to, from, cost);
/*for (auto i : tmp)
cout << i << " ";
cout << endl;*/
now = tmp.size() - 1;
//makeans
for (int i = 1; i <= m; i++)
{
int ans = q[i];//当前询问的值
if (ok[i])continue;//已存在，跳过
for (int j = last; j <= now; j++)//遍历当前的子树可以得到的路径长度
if (ans >= tmp[j] && cnt[ans - tmp[j]])//桶中有这样的值
{
ok[i] = 1;//存在
break;
}
}
//insert_cnt
for (int i = last; i <= now; i++)
if (tmp[i] <= 10000000)
cnt[tmp[i]] = 1;
}
//clear_cnt
for (auto i : tmp)
if (i <= 10000000)
cnt[i] = 0;
}
void divid(int from)
{
vis[from] = 1;
cal(from);
for (int i = head[from]; ~i; i = e[i].next)
{
int to = e[i].to;
if (vis[to])continue;
tot = siz[to];
root = 0;
find(to, from);
divid(root);
}
}
int main()
{
fastio;
memset(head, -1, sizeof(head));
cin >> n >> m;
for (int i = 1; i < n; i++)
{
int x, y, z;
cin >> x >> y >> z;
add(x, y, z);
add(y, x, z);
}
for (int i = 1; i <= m; i++)
cin >> q[i];
mx[0] = n;
cnt[0] = 1;
root = 0;
find(1, 0);
divid(root);
for (int i = 1; i <= m; i++)
if (ok[i])
cout << "AYE" << endl;
else
cout << "NAY" << endl;
return 0;
}
P2634 [国家集训队]聪聪可可
模版题，没有任何其他操作，直接开个cnt[3]来点分算贡献就行了。
需要注意一点，除了root子树之间的贡献之外，还有对于root子树上的某个点x，x到root，x和x的贡献。
#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define fastio ios::sync_with_stdio(false),cin.tie(NULL),cout.tie(NULL)
using namespace std;
const ll mod = 998244353;
const int maxn = 1e5 + 5;
const int inf = 1e9 + 7;
const ll lnf = 1e18;
struct edge {
int to, cost, next;
}e[maxn << 1];
int edge_cnt = 0, head[maxn];
void add(int from, int to,int cost)
{
e[++edge_cnt] = { to,cost, head[from] };
head[from] = edge_cnt;
}
int siz[maxn], tot, mx[maxn];
int root = 0;
bool vis[maxn];
int n, m;
void find(int from, int fa)//找重心
{
siz[from] = 1, mx[from] = 0;
for (int i = head[from]; ~i; i = e[i].next)
{
int to = e[i].to;
if (to == fa || vis[to])continue;
find(to, from);
siz[from] += siz[to];
mx[from] = max(mx[from], siz[to]);
}
mx[from] = max(mx[from], tot - siz[from]);
if (mx[from] < mx[root])
root = from;
}
int cnt[4];
vector<int>tmp;
void getdis(int from, int fa, int res)
{
tmp.push_back(res % 3);
for (int i = head[from]; ~i; i = e[i].next)
{
int to = e[i].to, cost = e[i].cost;
if (vis[to] || to == fa)continue;
getdis(to, from, res + cost);
}
}
int res = 0;
void cal(int from)
{
tmp.clear();
int last, now;
for (int i = head[from]; ~i; i = e[i].next)
{
int to = e[i].to, cost = e[i].cost;
if (vis[to])continue;
last = tmp.size();
getdis(to, from, cost);
now = tmp.size() - 1;
//makeans
for (int i = last; i <= now; i++)
{
if (tmp[i] == 1)
res += 2 * cnt[2];
else if (tmp[i] == 2)
res += 2 * cnt[1];
else
res += 2 * cnt[0] + 2;//加2是root和x以及x和root
}
//insert_cnt
for (int i = last; i <= now; i++)
cnt[tmp[i]]++;
}
//clear_cnt
cnt[0] = cnt[1] = cnt[2] = 0;
}
void divid(int from)
{
vis[from] = 1;
cal(from);
for (int i = head[from]; ~i; i = e[i].next)
{
int to = e[i].to;
if (vis[to])continue;
tot = siz[to];
root = 0;
find(to, from);
divid(root);
}
}
int gcd(int a, int b)
{
return b ? gcd(b, a % b) : a;
}
int main()
{
fastio;
memset(head, -1, sizeof(head));
cin >> n;
int ans = n * n;
for (int i = 1; i < n; i++)
{
int x, y, z;
cin >> x >> y >> z;
add(x, y, z);
add(y, x, z);
}
mx[0] = n;
root = 0;
find(1, 0);
divid(root);
//cout << res<<" "<<ans << endl;
res += n;
int g = gcd(res, ans);
cout << res / g << "/" << ans / g;
return 0;
}