过年摸鱼了一个星期
周六
P3806 【模板】点分治1
用来处理树上的路径问题
其实挺暴力的，但是按照重心分解来处理却是nlogn的
#include <bits/stdc++.h>
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
#define rep(i, a, b) for(int i = (a); i < (b); i++)
using namespace std;const int N = 1e4 + 10;
const int M = 1e7 + 10;
vector<pair<int, int>> g[N];
int q[N], ans[N], maxp[N], vis[N], siz[N], rt, sum, n, m;
vector<int> ve;
bool judge[M];void getrt(int u, int fa)
{siz[u] = 1; maxp[u] = 0; //注意这里初始化maxpfor(auto x: g[u]){int v = x.first, w = x.second;if(v == fa || vis[v]) continue;getrt(v, u);siz[u] += siz[v];maxp[u] = max(maxp[u], siz[v]);}maxp[u] = max(maxp[u], sum - siz[u]);if(maxp[u] < maxp[rt]) rt = u;
}void getdis(int u, int fa, int d)
{if(d <= 1e7) ve.push_back(d); //询问到1e7 总和会到1e8for(auto x: g[u]){int v = x.first, w = x.second;if(vis[v] || v == fa) continue;getdis(v, u, d + w);}
}void solve(int u)
{vector<int> tmp; //防止memsetfor(auto x: g[u]){int v = x.first, w = x.second;if(vis[v]) continue;ve.clear();getdis(v, u, w);for(int x: ve)_for(i, 1, m)if(q[i] >= x)ans[i] |= judge[q[i] - x];for(int x: ve){judge[x] = true;tmp.push_back(x);}}for(int x: tmp) judge[x] = false;
}void divide(int u)
{vis[u] = 1; //删除usolve(u); //处理经过u的路径for(auto x: g[u]){int v = x.first;if(vis[v]) continue;maxp[rt = 0] = sum = siz[v]; //这里初始化sum是siz[v]getrt(v, 0);getrt(rt, 0);divide(rt);}
}int main()
{scanf("%d%d", &n, &m);_for(i, 1, n - 1){int u, v, w;scanf("%d%d%d", &u, &v, &w);g[u].push_back({v, w});g[v].push_back({u, w});}_for(i, 1, m) scanf("%d", &q[i]);judge[0] = true; //注意要初始化0maxp[rt = 0] = sum = n; //初始化rtgetrt(1, 0); //找重心getrt(rt, 0); //更新正确的siz数组divide(rt);_for(i, 1, m) puts(ans[i] ? "AYE" : "NAY");return 0;
}
P2634 [国家集训队]聪聪可可（点分治）
和上一道题很像，有一个坑点
处理出来的是路径的条数，而这道题(1, 2)和(2, 1)是不一样的
所以得出答案之后要处理一下
#include <bits/stdc++.h>
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
#define rep(i, a, b) for(int i = (a); i < (b); i++)
using namespace std;typedef long long ll;
const int N = 2e4 + 10;
vector<pair<int, int>> g[N];
int maxp[N], siz[N], vis[N], rt, sum, n;
vector<int> ve;
ll ans, cnt[3];void getrt(int u, int fa)
{maxp[u] = 0; siz[u] = 1;for(auto x: g[u]){int v = x.first, w = x.second;if(vis[v] || v == fa) continue;getrt(v, u);siz[u] += siz[v];maxp[u] = max(maxp[u], siz[v]);}maxp[u] = max(maxp[u], sum - siz[u]);if(maxp[rt] > maxp[u]) rt = u;
}void getdis(int u, int fa, int d)
{ve.push_back(d);for(auto x: g[u]){int v = x.first, w = x.second;if(vis[v] || v == fa) continue;getdis(v, u, d + w);}
}void solve(int u)
{ans++; //自己到自己cnt[1] = cnt[2] = 0; cnt[0] = 1;for(auto x: g[u]){int v = x.first, w = x.second;if(vis[v]) continue;ve.clear();getdis(v, u, w);for(int x: ve)rep(i, 0, 3)if((x + i) % 3 == 0)ans += cnt[i];for(int x: ve) cnt[x % 3]++;}
}void divide(int u)
{vis[u] = 1;solve(u);for(auto x: g[u]){int v = x.first, w = x.second;if(vis[v]) continue;maxp[rt = 0] = sum = siz[v];getrt(v, 0);getrt(rt, 0);divide(rt);}
}ll gcd(ll a, ll b) { return !b ? a : gcd(b, a % b); }int main()
{scanf("%d", &n);_for(i, 1, n - 1){int u, v, w;scanf("%d%d%d", &u, &v, &w);w %= 3;g[u].push_back({v, w});g[v].push_back({u, w});}maxp[rt = 0] = sum = n;getrt(1, 0);getrt(rt, 0);divide(rt);ll a = (ans - n) * 2 + n, b = 1LL * n * n;ll d = gcd(a, b);printf("%lld/%lld\n", a / d, b / d);return 0;
}
P4149 [IOI2011]Race（点分治）
用unordered_map存一下之前子树中。权值和为x的最少边数即可
#include <bits/stdc++.h>
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
#define rep(i, a, b) for(int i = (a); i < (b); i++)
using namespace std;typedef long long ll;
const int N = 2e5 + 10;
vector<pair<int, int>> g[N];
int maxp[N], siz[N], vis[N], rt, sum, n, k, ans = 1e9;
vector<pair<int, int>> ve;void getrt(int u, int fa)
{maxp[u] = 0; siz[u] = 1;for(auto x: g[u]){int v = x.first, w = x.second;if(vis[v] || v == fa) continue;getrt(v, u);siz[u] += siz[v];maxp[u] = max(maxp[u], siz[v]);}maxp[u] = max(maxp[u], sum - siz[u]);if(maxp[rt] > maxp[u]) rt = u;
}void getdis(int u, int fa, int d, int dep)
{if(d > k) return;ve.push_back({d, dep});for(auto x: g[u]){int v = x.first, w = x.second;if(vis[v] || v == fa) continue;getdis(v, u, d + w, dep + 1);}
}void solve(int u)
{unordered_map<int, int> mp;for(auto x: g[u]){int v = x.first, w = x.second;if(vis[v]) continue;ve.clear();getdis(v, u, w, 1);for(auto x: ve){if(k > x.first && mp[k - x.first]) ans = min(ans, mp[k - x.first] + x.second);if(k == x.first) ans = min(ans, x.second);}for(auto x: ve){if(!mp[x.first]) mp[x.first] = x.second;else mp[x.first] = min(mp[x.first], x.second);}}
}void divide(int u)
{vis[u] = 1;solve(u);for(auto x: g[u]){int v = x.first, w = x.second;if(vis[v]) continue;maxp[rt = 0] = sum = siz[v];getrt(v, 0);getrt(rt, 0);divide(rt);}
}int main()
{scanf("%d%d", &n, &k);_for(i, 1, n - 1){int u, v, w;scanf("%d%d%d", &u, &v, &w);u++; v++;g[u].push_back({v, w});g[v].push_back({u, w});}maxp[rt = 0] = sum = n;getrt(1, 0);getrt(rt, 0);divide(rt);printf("%d\n", ans == 1e9 ? -1 : ans);return 0;
}
P4178 Tree（点分治+树状数组）
和前面差不多
需要用一个数据结构来维护前缀和，单点修改
树状数组即可
注意细节，树状数组不能处理0，因此在求和的时候初始化为1
#include <bits/stdc++.h>
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
#define rep(i, a, b) for(int i = (a); i < (b); i++)
using namespace std;typedef long long ll;
const int N = 4e4 + 10;
vector<pair<int, int>> g[N];
int maxp[N], vis[N], siz[N], cnt[N], f[N], rt, sum, n, m, k;
vector<int> ve;
ll ans;void getrt(int u, int fa)
{siz[u] = 1; maxp[u] = 0;for(auto x: g[u]){int v = x.first, w = x.second;if(v == fa || vis[v]) continue;getrt(v, u);siz[u] += siz[v];maxp[u] = max(maxp[u], siz[v]);}maxp[u] = max(maxp[u], sum - siz[u]);if(maxp[u] < maxp[rt]) rt = u;
}void getdis(int u, int fa, int d)
{if(d > k) return;ve.push_back(d);for(auto x: g[u]){int v = x.first, w = x.second;if(vis[v] || v == fa) continue;getdis(v, u, d + w);}
}int lowbit(int x) { return x & -x; }void add(int x)
{for(; x <= k; x += lowbit(x))f[x]++;
}int cal(int x)
{int res = 1;for(; x; x -= lowbit(x))res += f[x];return res;
}void solve(int u)
{memset(f, 0, sizeof f);for(auto x: g[u]){int v = x.first, w = x.second;if(vis[v]) continue;ve.clear();getdis(v, u, w);for(int x: ve) ans += cal(k - x);for(int x: ve) add(x);}
}void divide(int u)
{vis[u] = 1;solve(u);for(auto x: g[u]){int v = x.first;if(vis[v]) continue;maxp[rt = 0] = sum = siz[v];getrt(v, 0);getrt(rt, 0);divide(rt);}
}int main()
{scanf("%d", &n);_for(i, 1, n - 1){int u, v, w;scanf("%d%d%d", &u, &v, &w);g[u].push_back({v, w});g[v].push_back({u, w});}scanf("%d", &k);maxp[rt = 0] = sum = n;getrt(1, 0);getrt(rt, 0);divide(rt);printf("%lld\n", ans);return 0;
}