点分治
什么是点分治？
点分治主要用于有关树上路径统计的问题。
怎么点分治？
1，选取一个点，把树变成有根树。为了让递归层数尽可能的小，我们要选取树的重心，即子树大小最大值最小的点。
2，处理联通块中通过根的路径。
3，删除根节点。
4，递归处理子树。
操作
1 void getR(int u, int f) {2 sz[u] = 1; mx[u] = 0;3 for (int v, i = 0; i < g[u].size(); ++i) if ((v = g[u][i].v) != f && !vis[v]) {4 getR(v, u); sz[u] += sz[v]; gmax(mx[u], sz[v]);5 } gmax(mx[u], size - sz[u]);6 if (mx[R] > mx[u]) R = u;7 }8 //找重心 例题们
1 #include2 #include 3 #include 4 #include 5 #include 6 using namespace std; 7 inline char nc() { 8 static char b[1<<15],*s=b,*t=b; 9 return s==t&&(t=(s=b)+fread(b,1,1<<15,stdin),s==t)?-1:*s++;10 }11 inline void read(int &x) {12 char b = nc(); x = 0;13 for (; !isdigit(b); b = nc());14 for (; isdigit(b); b = nc()) x = x * 10 + b - '0';15 }16 const int N = 10010;17 int n, m, R, sz[N], msz[N], ans, size, dep[N], D, d[N];18 struct Edge { int v,w;};19 vector < Edge > g[N];20 bitset < N > vis;21 inline void ae(int u, int v, int w) {22 g[u].push_back((Edge){v, w});23 g[v].push_back((Edge){u, w});24 }25 void getR(int u, int f) {26 sz[u] = 1; msz[u] = 0;27 for (int v, i = 0; i < g[u].size(); ++i) if ((v = g[u][i].v) != f && !vis[v]) {28 getR(v, u); sz[u] += sz[v]; msz[u] = max(msz[u], sz[v]);29 } msz[u] = max(msz[u], size - sz[u]);30 if (msz[u] < msz[R]) R = u;31 }32 void getD(int u, int f) {33 d[++D] = dep[u];34 for (int v, i = 0; i < g[u].size(); ++i)35 if ((v = g[u][i].v) != f && !vis[v])36 dep[v] = dep[u] + g[u][i].w, getD(v, u);37 }38 int calc(int u) {39 D = 0; getD(u, 0);40 sort(d + 1, d + 1 + D);41 int res = 0, l = 1, r = D;42 while (l < r) {43 if (d[l] + d[r] <= m) res += r - l, ++l;44 else --r;45 } return res;46 }47 void solve(int u) {48 dep[u] = 0; vis[u] = 1; ans += calc(u);49 for (int v, i = 0; i < g[u].size(); ++i) {50 if (!vis[v = g[u][i].v]) {51 dep[v] = g[u][i].w;52 ans -= calc(v);53 size = sz[v];54 getR(v, R = 0); 55 solve(R);56 }57 }58 }59 void solve() {60 for (int i = 1, u, v, w; i < n; ++i)61 read(u), read(v), read(w), ae(u, v, w);62 size = n; getR(1, R = 0); solve(R);63 printf("%d\n", ans); ans = 0;64 for (int i = 1; i <= n; ++i) g[i].clear(); 65 vis.reset();66 }67 int main() {68 msz[0] = 0x3f3f3f3f;69 while (read(n), read(m), n + m) solve();70 return 0;71 }
1 #include2 #include 3 #include 4 #include 5 #include 6 #define fir first 7 #define pb push_back 8 #define sec second 9 using namespace std;10 inline char nc() {11 static char b[1<<16],*s=b,*t=b;12 return s==t&&(t=(s=b)+fread(b,1,1<<16,stdin),s==t)?-1:*s++;13 }14 template < class T >15 inline void read(T &x) {16 char b = nc(); x = 0;17 for (; !isdigit(b); b = nc());18 for (; isdigit(b); b = nc()) x = x * 10 + b - '0';19 }20 typedef long long ll;21 const int N = 10010;22 int n, m, sz[N], R, mx[N], size;23 ll dis[N];24 set < int > s;25 bitset < N > vis;26 struct Edge { int v,w;};27 pair < ll , bool > q[110];28 vector < Edge > g[N];29 inline void ae(int u, int v, int w) {30 g[u].pb((Edge){v, w});31 g[v].pb((Edge){u, w});32 }33 inline void gmax(int &x, int y) {34 if (x < y) x = y; 35 }36 void getR(int u, int f) {37 sz[u] = 1; mx[u] = 0;38 for (int v, i = 0; i < g[u].size(); ++i) if ((v = g[u][i].v) != f && !vis[v]) {39 getR(v, u); sz[u] += sz[v]; gmax(mx[u], sz[v]);40 } gmax(mx[u], size - sz[u]);41 if (mx[R] > mx[u]) R = u;42 }43 inline void upd(ll x) {44 for (int i = 1; i <= m; ++i)45 if (!q[i].sec && s.count(q[i].fir - x)) q[i].sec = 1;46 }47 void calc(int u, int f) {48 upd(dis[u]);49 for (int i = 0, v; i < g[u].size(); ++i)50 if ((v = g[u][i].v) != f && !vis[v])51 dis[v] = dis[u] + g[u][i].w, calc(v, u);52 }53 void add(int u, int f) {54 s.insert(dis[u]);55 for (int i = 0, v; i < g[u].size(); ++i)56 if ((v = g[u][i].v) != f && !vis[v]) add(v, u);57 }58 void solve(int u) {59 vis[u] = 1; dis[u] = 0; s.clear(); s.insert(0);60 for (int v, i = 0; i < g[u].size(); ++i) if (!vis[v = g[u][i].v]) {61 dis[v] = g[u][i].w; calc(v, u); add(v, u);62 }63 for (int v, i = 0; i < g[u].size(); ++i) if (!vis[v = g[u][i].v]) {64 size = sz[v]; getR(v, R = 0); solve(R); 65 }66 }67 int main() {68 read(n); read(m); mx[0] = ~0U >> 1;69 for (int u, v, w, i = 1; i < n; ++i)70 read(u), read(v), read(w), ae(u, v, w);71 for (int i = 1; i <= m; ++i) read(q[i].fir);72 size = n; getR(1, 1); solve(R);73 for (int i = 1; i <= m; ++i) puts(q[i].fir == 0 || q[i].sec ? "Yes" : "No");74 return 0; 75 }76 //bzoj1316
入门题。
题意：找出距离$ \leqslant m$的点对的数目。
为了不重复计算，咱每次都统计必须经过根节点的满足条件的路径的条数。
要统计在某子树中满足条件的路径，咱只要把子树中每一点到根的距离都算出来，排序，扫一次就行。
必须经过根节点的满足条件的路径的条数为$calc(u) - \Sigma calc(v)$。
1 #include2 #include 3 #include 4 #include 5 using namespace std; 6 inline char nc() { 7 static char b[1<<16],*s=b,*t=b; 8 return s==t&&(t=(s=b)+fread(b,1,1<<16,stdin),s==t)?-1:*s++; 9 }10 inline void read(int &x) {11 char b = nc(); x = 0;12 for (; !isdigit(b); b = nc());13 for (; isdigit(b); b = nc()) x = x * 10 + b - '0';14 }15 const int N = 200005;16 struct Edge { int v,w;};17 vector < Edge > g[N];18 inline void ae(int u, int v, int w) {19 g[u].push_back((Edge){v, w});20 g[v].push_back((Edge){u, w});21 }22 int n, m, R, sz[N], mx[N], size, dep[N], ans, dis[N];23 bitset < N > vis;24 int h[1000010], T[1000010], D;25 inline void gmin(int &x, int y) { if (x > y) x = y;}26 inline void gmax(int &x, int y) { if (x < y) x = y;}27 void getR(int u, int f) {28 sz[u] = 1; mx[u] = 0;29 for (int v, i = 0; i < g[u].size(); ++i) 30 if ((v = g[u][i].v) != f && !vis[v]) {31 getR(v, u); sz[u] += sz[v]; gmax(mx[u], sz[v]);32 } gmax(mx[u], size - sz[u]);33 if (mx[R] > mx[u]) R = u;34 }35 inline void query(int x, int y) {36 if (x <= m && T[m-x] == D) gmin(ans, y + h[m-x]);37 }38 inline void upd(int x, int y) {39 if (T[x] == D) gmin(h[x], y); else h[x] = y, T[x] = D;40 }41 void calc(int u, int f) {42 dep[u] = dep[f] + 1; query(dis[u], dep[u]);43 for (int v, i = 0; i < g[u].size(); ++i)44 if ((v = g[u][i].v) != f && !vis[v])45 dis[v] = dis[u] + g[u][i].w, calc(v, u);46 }47 void add(int u, int f) {48 if (dis[u] <= m) upd(dis[u], dep[u]);49 for (int v, i = 0; i < g[u].size(); ++i)50 if ((v = g[u][i].v) != f && !vis[v]) add(v, u);51 }52 void solve(int u) {53 vis[u] = 1; ++D; upd(dis[u] = 0, dep[u] = 0);54 for (int v, i = 0; i < g[u].size(); ++i) 55 if (!vis[v = g[u][i].v]) {56 dis[v] = g[u][i].w;57 calc(v, u); add(v, u);58 }59 for (int v, i = 0; i < g[u].size(); ++i) {60 if (!vis[v = g[u][i].v]) {61 size = sz[v];62 getR(v, R = 0);63 solve(R);64 }65 }66 }67 int main() {68 read(n); read(m); ans = ~0U >> 1; mx[0] = 0x3f3f3f3f;69 for (int i = 1, u, v, w; i < n; ++i)70 read(u), read(v), read(w), ae(++u, ++v, w);71 size = n; getR(1, 1); solve(R); 72 printf("%d\n", ans != ~0U >> 1 ? ans : -1);73 return 0;74 }
咱每次只统计经过了根节点的路径。所以要先统计子树答案在加入子树信息。
全局开一个数组，记录到根节点的长度为$x$时，最小的深度$h[x]$。
1 #include2 #include 3 #include 4 #include 5 using namespace std; 6 inline char nc() { 7 static char b[1<<16],*s=b,*t=b; 8 return s==t&&(t=(s=b)+fread(b,1,1<<16,stdin),s==t)?-1:*s++; 9 }10 inline void read(int &x) {11 char b = nc(); x = 0;12 for (; !isdigit(b); b = nc());13 for (; isdigit(b); b = nc()) x = x * 10 + b - '0';14 }15 const int N = 100005;16 struct Edge { int v,w;};17 vector < Edge > e[N];18 inline void ae(int u, int v, int w) {19 e[u].push_back((Edge){v, w});20 e[v].push_back((Edge){u, w});21 }22 int n, sz[N], mx[N], R, size, ff[N+N][2], gg[N+N][2], dis[N], dmx, hmx;23 long long ans;24 bitset < N > vis;25 int (*f)[2] = ff + 100000, (*g)[2] = gg + 100000;26 int cc[N+N], *c = cc + 100000;27 inline int ABS(int x) { return x > 0 ? x : -x;}28 inline void gmax(int &x, int y) {29 if (x < y) x = y; 30 }31 void getR(int u, int f) {32 sz[u] = 1; mx[u] = 0;33 for (int v, i = 0; i < e[u].size(); ++i)34 if ((v = e[u][i].v) != f && !vis[v]) {35 getR(v, u); sz[u] += sz[v]; gmax(mx[u], sz[v]);36 }37 gmax(mx[u], size - sz[u]);38 if (mx[R] > mx[u]) R = u;39 }40 void calc(int u, int f) {41 gmax(dmx, ABS(dis[u]));42 ++g[dis[u]][bool(c[dis[u]])];43 ++c[dis[u]];44 for (int v, i = 0; i < e[u].size(); ++i)45 if ((v = e[u][i].v) != f && !vis[v])46 dis[v] = dis[u] + e[u][i].w, calc(v, u);47 --c[dis[u]];48 }49 void solve(int u) {50 f[dis[u] = 0][0] = 1; vis[u] = 1; hmx = 0;51 for (int v, i = 0; i < e[u].size(); ++i)52 if (!vis[v = e[u][i].v]) {53 dmx = 0; dis[v] = e[u][i].w;54 calc(v, u); gmax(hmx, dmx);55 ans += (f[0][0]-1) * g[0][0];56 for (int j = -dmx; j <= dmx; ++j)57 ans += f[j][0] * g[-j][1] + f[j][1] * g[-j][0] + f[j][1] * g[-j][1];58 for (int j = -dmx; j <= dmx; ++j)59 f[j][0] += g[j][0], f[j][1] += g[j][1], g[j][0] = g[j][1] = 0;60 }61 for (int i = -hmx; i <= hmx; ++i) f[i][0] = f[i][1] = 0;62 for (int v, i = 0; i < e[u].size(); ++i)63 if (!vis[v = e[u][i].v]) {64 size = sz[v];65 getR(v, R = 0);66 solve(R);67 }68 }69 int main() {70 read(n); mx[0] = 0x3f3f3f3f; size = n;71 for (int i = 1, u, v, w; i < n; ++i)72 read(u), read(v), read(w), ae(u, v, w == 1 ? 1 : -1);73 getR(1, 1); solve(R);74 printf("%lld\n", ans);75 return 0;76 }
题意：边权有$1,-1$，求有多少条路径权值和为$0$，且从中间某点断开，剩下的两条路径的权值和也为$0$。
记$dis(u)$为当前根$r$到$u$的距离，$f(d,0/1)$为之前几棵子树中距离为$d$，是否出现过$d$这个权值的边的个数。$g(d,0/1)$则是当前子树的。
如果向下$dfs$时发现现在的距离$d$在$r-u$上是出现过的，说明$u$到之前出现$d$的点$v$的这一段距离为$0$。也就是说$u-v$边权和为$0$，用题目的说法就是阴阳平衡。
算出了$f$和$g$后就很好计算答案了，$ans = f(0,0) \times g(0,0) + \sum_d f(d,0) \times g(-d, 1) +f(d, 1) \times g(-d, 0) + f(d, 1) \times g(d, 1)$。
分别对应着休息点在根上，当前子树中，前几棵子树中的某一棵中，当前子树和前几棵子树的某一棵都行。
1 #include2 #include 3 #include 4 #include 5 #include 6 #define pb push_back 7 using namespace std; 8 inline char nc() { 9 static char b[1<<16],*s=b,*t=b;10 return s==t&&(t=(s=b)+fread(b,1,1<<16,stdin),s==t)?-1:*s++;11 }12 inline void read(int &x) {13 char b = nc(); x = 0;14 for (; !isdigit(b); b = nc());15 for (; isdigit(b); b = nc()) x = x * 10 + b - '0';16 }17 const int N = 100005;18 inline void gmax(int &x, int y) { if (x < y) x = y;}19 struct Node {20 Node *ch[2]; int v;21 } Tnull, *null = &Tnull, *root;22 Node mem[6000000], *C;23 inline Node* newNode() {24 C->ch[0] = C->ch[1] = null;25 C->v = 0; return C++;26 }27 void insert(int x, int v) {28 Node *u = root;29 for (int c, i = 30; ~i; --i) {30 c = (x >> i) & 1;31 if (u->ch[c] == null) 32 u->ch[c] = newNode();33 u = u->ch[c];34 gmax(u->v, v);35 } 36 }37 int query(int x, int v) {38 if (root == null) return -1;39 int res = 0; 40 Node *u = root;41 for (int c, i = 30; ~i; --i) {42 c = !((x >> i) & 1);43 if (u->ch[c] != null && u->ch[c]->v >= v)44 res |= 1 << i;45 else c = !c;46 u = u->ch[c];47 if (u->v < v) return -1;48 } return res;49 }50 vector < int > g[N];51 int n, m, val[N], sz[N], mx[N], R, ans, size;52 bitset < N > vis, a;53 inline void ae(int u, int v) {54 g[u].pb(v); g[v].pb(u);55 }56 void getR(int u, int f) {57 sz[u] = 1; mx[u] = 0;58 for (int v,i = 0; i < g[u].size(); ++i) if ((v = g[u][i]) != f && !vis[v]) {59 getR(v, u); sz[u] += sz[v]; gmax(mx[u], sz[v]);60 } gmax(mx[u], size - sz[u]);61 if (mx[R] > mx[u]) R = u;62 }63 void calc(int u, int f, int w, int c) {64 gmax(ans, query(w, m - c));65 for (int v, i = 0; i < g[u].size(); ++i) 66 if ((v = g[u][i]) != f && !vis[v]) {67 calc(v, u, w ^ val[v], c + a[v]);68 }69 }70 void add(int u, int f, int w, int c) {71 insert(w, c);72 for (int v, i = 0; i < g[u].size(); ++i)73 if ((v = g[u][i]) != f && !vis[v])74 add(v, u, w ^ val[v], c + a[v]);75 }76 void solve(int u) {77 vis[u] = 1; C = mem; root = newNode(); insert(0, 0);78 for (int v, i = 0; i < g[u].size(); ++i) if (!vis[v = g[u][i]]) {79 calc(v, u, val[u] ^ val[v], a[u] + a[v]);80 add(v, u, val[v], a[v]);81 } gmax(ans, query(val[u], m - a[u]));82 for (int v, i = 0; i < g[u].size(); ++i) if (!vis[v = g[u][i]]) {83 size = sz[v]; getR(v, R = 0); solve(R);84 }85 }86 int main() {87 null->ch[0] = null->ch[1] = null;88 ans = -1; mx[0] = ~0U >> 1;89 read(n); read(m);90 for (int i = 1, t; i <= n; ++i)91 read(t), a[i] = t;92 if (a.count() < m) return puts("-1"), 0;93 for (int i = 1; i <= n; ++i) read(val[i]);94 for (int i = 1, u, v; i < n; ++i)95 read(u), read(v), ae(u, v);96 size = n; getR(1, 1); solve(R);97 printf("%d\n", ans);98 return 0;99 }
题意：有喜欢的点，点上有点权。求出一条路径使得点权异或和最大且有至少$k$个喜欢的点在路径上。
$k=0$时的原题：
要让异或和最大，当然还是在$trie$上贪心。
还是跟上面的套路一样，咱只统计经过了根节点的路径。
咱往$trie$里插入异或和时不计算根的值，算时把根加进去。这样就不会把根的异或掉。
在$trie$里还要额外记录路径上喜欢的节点的个数。