## 【BZOJ 3451】Tyvj1953 Normal

### 解题报告

—————————— UPD 2017.4.11 ————————————

## 【BZOJ 4182】Shopping

### 解题报告

—————————— UPD 2017.3.19 ——————————

## 【日常小测】路径规划

### Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 300009;
const int M = N << 1;
const int INF = 1e9;

LL vout;

inline void Add_Edge(int u, int v, int c) {
static int E = 1;
to[++E] = v; nxt[E] = head[u]; head[u] = E; cost[E] = c;
to[++E] = u; nxt[E] = head[v]; head[v] = E; cost[E] = c;
}

char c=getchar(); int ret=0,f=1;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret * f;
}

class Divide_and_Conquer{
int rt,rt_sz,blk_sz,tot,sz[N],vis[N];
struct Data{
int mn,id; LL sum;
inline bool operator < (const Data &B) const {
return mn < B.mn;
}
}sta[N];
public:
void solve(int w, int blk) {
GetRoot(w, blk); vis[w=rt] = 1; tot = 0;
if (!vis[to[i]]) {
DFS(to[i], w, to[i], cost[i], cost[i]);
}
}
if (tot) update();
if (!vis[to[i]]) {
if (sz[to[i]] > sz[w]) sz[to[i]] = blk - sz[w];
solve(to[i], sz[to[i]]);
}
}
}
private:
inline void update() {
sort(sta+1, sta+1+tot);
LL mx1=0,mx2=0; int sur1=0,sur2=0;
for (int i=tot;i;i--) {
vout = max(vout, sta[i].mn * sta[i].sum);
if (sur1 && sur1 != sta[i].id) {
vout = max(vout, (mx1 + sta[i].sum) * sta[i].mn);
} else if (sur2 && sur2 != sta[i].id) {
vout = max(vout, (mx2 + sta[i].sum) * sta[i].mn);
}
if (sta[i].sum > mx1) {
if (sur1 == sta[i].id) {
mx1 = sta[i].sum;
} else {
mx2 = mx1; sur2 = sur1;
mx1 = sta[i].sum; sur1 = sta[i].id;
}
} else if (sta[i].sum > mx2) {
if (sur1 != sta[i].id) {
sur2 = sta[i].id;
mx2 = sta[i].sum;
}
}
}
}
inline void GetRoot(int w, int blk) {
rt_sz = INF; blk_sz = blk;
GetRoot1(w, w);
}
void GetRoot1(int w, int f) {
sz[w] = 1; int mx = 1;
if (to[i] != f && !vis[to[i]]) {
GetRoot1(to[i], w);
sz[w] += sz[to[i]];
mx = max(mx, sz[to[i]]);
}
}
mx = max(mx, blk_sz - sz[w]);
if (mx < rt_sz) rt_sz = mx, rt = w;
}
void DFS(int w, int f, int top, int mn, LL sum) {
bool tag = 1;
if (to[i] != f && !vis[to[i]]) {
DFS(to[i], w, top, mn>cost[i]?cost[i]:(tag=0,mn), cost[i] + sum);
}
}
if (!tag) return;
sta[++tot].mn = mn; sta[tot].id = top; sta[tot].sum = sum;
}
}DAC;

int main() {
for (int i=1,u,v;i<n;i++) {
}
DAC.solve(1, n);
printf("%lld\n",vout);
return 0;
}


#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 300009;
const int M = N << 1;

int stp[N],p[N][2],fa[N][20],anc[N];
struct Edge{int u,v,c;}e[N];
LL vout,dep[N],MX[N];

char c=getchar(); int ret=0,f=1;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret*f;
}

void DFS(int w, int f) {
fa[w][0] = f; stp[w] = stp[f] + 1;
if (to[i] != f) {
dep[to[i]] = dep[w] + cost[i];
DFS(to[i], w);
}
}
}

inline void AddEdge(int u, int v, int c, int id) {
static int E = 1; cost[E+1] = cost[E+2] = c;
e[id] = (Edge){u, v, c};
}

inline LL Dis(int u, int v) {
if (stp[v] < stp[u]) swap(u, v); int p1 = u, p2 = v;
for (int i=19;~i;i--) if (stp[fa[v][i]]>=stp[u]) v = fa[v][i];
if (u == v) return dep[p2] - dep[u];
for (int i=19;~i;i--) if (fa[u][i]!=fa[v][i]) u=fa[u][i],v=fa[v][i];
return -(dep[fa[u][0]]<<1) + dep[p1] + dep[p2];
}

int find(int x) {return anc[x]==x?x:anc[x]=find(anc[x]);}

inline LL Merge(int u, int v) {
static LL ret, p1, p2; u = find(u); v = find(v);
if (MX[u] > MX[v]) ret = MX[u], p1 = p[u][0], p2 = p[u][1];
else ret = MX[v], p1 = p[v][0], p2 = p[v][1];
for (int i=0;i<=1;i++) {
for (int j=0;j<=1;j++) {
LL cur = Dis(p[u][i], p[v][j]);
if (cur > ret) {
ret = cur;
p1 = p[u][i];
p2 = p[v][j];
}
}
}
anc[u] = v; MX[v] = ret;
p[v][0] = p1; p[v][1] = p2;
return ret;
}

int main() {
for (int i=1,u,v;i<n;i++) {
}
DFS(1, 1);
for (int j=1;j<20;j++) {
for (int i=1;i<=n;i++) {
fa[i][j] = fa[fa[i][j-1]][j-1];
}
}
sort(e+1, e+N, [](const Edge &A, const Edge &B){return A.c > B.c;});
for (int i=1;i<=n;i++) {
anc[i] = i;
p[i][0] = p[i][1] = i;
}
for (int i=1;i<n;i++) {
LL tmp = Merge(e[i].u, e[i].v);
vout = max(vout, tmp * e[i].c);
}
printf("%lld\n",vout);
return 0;
}


## 【HackerRank】Unique Colors

### 解题报告

##### Ⅰ.点分治的做法 $$O(n\log (n))$$

1. 点3点1 的简单路径上没有染色点
那么贡献为$${T_1} – {T_3}$$
2. 点3点1 的简单路径上有染色点
那么贡献为$${S_1} – {S_2}$$

1. 到分支点的路径上出现过该颜色
2. 到分治点的路径上没有出现过该颜色

## 【CodeChef BTREE】Union on Tree

### 解题报告

##### 1）函数式线段树的做法

1. v不是u在虚树中的祖先，统计v的子树中、到u的距离为d的点的个数
这个的话，直接用函数式线段树查就好
2. v是u的父亲，其余条件相同
这样的话，似乎与v的距离就不固定了（lca在u ~ v中移动）
于是先用点分治做出所有点到u的距离为d的点的个数n1
然后需要减掉v子树外的部分，这样的话，发现到v的距离就固定了
于是减掉所有点到v的距离为d-dis(u,v)的点数n2
再加上v子树中到v距离为d-dis(u,v)的点数n3就可以辣！

### Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 100000 + 9;
const int M = N << 1;
const int INF = 1e8;

int anc[N][18],dep[N],val[N],p[N];

char c=getchar(); int f=1,ret=0;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret * f;
}

inline void Add_Edge(int u, int v) {
}

void DFS(int w, int f) {
static int cnt = 0;
dep[w] = dep[f] + 1;
anc[w][0] = f; num[w] = ++cnt;
if (!dep[to[i]]) {
DFS(to[i], w);
}
}
}

inline int LCA(int x, int y) {
if (dep[x] < dep[y]) swap(x, y);
for (int i=17;~i;i--)
if (dep[anc[x][i]] >= dep[y])
x = anc[x][i];
if (x == y) return x;
for (int i=17;~i;i--) {
if (anc[x][i] != anc[y][i]) {
x = anc[x][i];
y = anc[y][i];
}
}
return anc[x][0];
}

inline int dis(int x, int y) {
int lca = LCA(x, y);
return dep[x] + dep[y] - dep[lca] * 2;
}

class Point_Based_Divide_and_Conquer{
int fa[N][18],tot[N],sum[N];
int ans_tmp,root,block_size;
vector<int> q[N],mul[N];
bool vis[N];

public:
inline void init() {
block_size = n;
ans_tmp = INF;
Get_Root(1, 1);
tot[root] = 1;
build(root, n);
}

inline int query(int w, int rag) {
int ret = Query(w, rag, q);
for (int i=1,t;i<tot[w];i++) {
t = rag - dis(fa[w][i], w);
if (t >= 0) {
ret += Query(fa[w][i], t, q);
ret -= Query(fa[w][i-1], t, mul);
}
}
return ret;
}
private:
void Get_Root(int w, int f) {
int mx = 0; sum[w] = 1;
if (to[i] != f && !vis[to[i]]) {
Get_Root(to[i], w);
mx = max(mx, sum[to[i]]);
sum[w] += sum[to[i]];
}
}
mx = max(block_size - sum[w], mx);
if (mx < ans_tmp) {
ans_tmp = mx;
root = w;
}
}

void build(int w, int sz) {
vis[w] = 1; fa[w][0] = w;
if (!vis[to[i]]) {
block_size = sum[to[i]] < sum[w] ? sum[to[i]] : sz - sum[w];
ans_tmp = INF; Get_Root(to[i], w);
memcpy(fa[root]+1, fa[w], sizeof(fa[w])-sizeof(int));
tot[root] = tot[w] + 1;
build(root, block_size);
}
}

if (val[w]) {
for (int i=0;i<tot[w];i++)
q[fa[w][i]].push_back(dis(w, fa[w][i]));
for (int i=0;i<tot[w]-1;i++)
mul[fa[w][i]].push_back(dis(w, fa[w][i+1]));
}
sort(q[w].begin(), q[w].end());
sort(mul[w].begin(), mul[w].end());
}

inline int Query(int w, int r, vector<int> *a) {
return upper_bound(a[w].begin(), a[w].end(), r) - a[w].begin();
}
}PDC;

class Virtual_Tree{
int stk[N],rag[N],top,lca,cnt,root;
queue<int> que;
bool inq[N];

public:
inline void build(int &tot) {
cnt = tot; T = 0;
for (int i=2;i<=tot;i++) {
root = LCA(root, p[i]);
}
static auto cmp = [](int a, int b) {return num[a] < num[b];};
sort(p+1, p+1+tot, cmp);
if (root != p[1]) p[++tot] = root, newnode(root, -1);
stk[top=1] = root;
for (int i=1+(p[1]==root);i<=cnt;i++) {
lca = LCA(p[i], stk[top]);
for (;dep[stk[top]] > dep[lca];top--)
if (dep[stk[top-1]] >= dep[lca]) AddEdge(stk[top-1], stk[top]);
if (lca != stk[top])
stk[++top] = p[++tot] = lca;
if (p[i] != stk[top])
stk[++top] = p[i];
}
for (int i=1;i<top;i++)
}

inline int solve(int tot) {
prework(tot);
int ret = 0;
for (int i=1,u,v,r,mid,t;i<T;i+=2) {
u = to[i]; v = to[i+1];
r = rag[u] + rag[v] - cost[i] >> 1;
if (r >= 0) {
mid = move(u, v, r);
ret -= PDC.query(mid, r);
}
}
for (int i=1;i<=tot;i++)
ret += PDC.query(p[i], rag[p[i]]);
return ret;
}
private:
inline void newnode(int w, int v) {
rag[w] = v << 1;
}

inline int move(int x, int y, int r) {
if (dep[x] < dep[y]) swap(x, y);
r = rag[x] - r;
for (int i=0;r;i++,r>>=1)
if (r & 1) x = anc[x][i];
return x;
}

inline void prework(int tot) {
for (int i=1;i<=tot;i++) {
que.push(p[i]);
inq[p[i]] = 1;
}

while (!que.empty()) {
int w = que.front();
que.pop(); inq[w] = 0;
if (rag[w] > rag[to[i]] + cost[i]) {
rag[to[i]] = rag[w] - cost[i];
if (!inq[to[i]]) inq[to[i]] = 1, que.push(to[i]);
}
}
}
}

inline void AddEdge(int u, int v) {
int w = dis(u, v);
to[++T] = v; nxt[T] = head[u]; head[u] = T; cost[T] = w;
to[++T] = u; nxt[T] = head[v]; head[v] = T; cost[T] = w;
}
}VT;

int main() {
fill(val+1, val+1+n, 1);
for (int i=1,lim=n,u,v;i<lim;i++) {
}

DFS(1, 1);
for (int j=1;j<=17;j++) {
for (int i=1;i<=n;i++) {
anc[i][j] = anc[anc[i][j-1]][j-1];
}
}
PDC.init();

for (int y=1,k;y<=m;y++) {
printf("%d\n",VT.solve(k));
}
return 0;
}


## 【CodeChef PRIMEDST】Prime Distance On Tree

### 解题报告

$$\sum\limits_{i + j = prime\_number} {nu{m_i} \cdot nu{m_j}}$$

### Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 66000;
const int M = 110000;
const int INF = 1e9;
const double EPS = 1e-2;
const double PI = acos(-1);

LL vout;

inline void Add_Edge(int u, int v) {
static int T = 0;
}

char c=getchar(); int f=1,ret=0;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret * f;
}

class Fast_Fourier_Transform{
typedef complex<double> E;
complex<double> a[N<<1];
int pri[M],vis[M],pos[N<<1],tot,len,stp;
public:
Fast_Fourier_Transform() {
for (int i=2;i<M;i++) {
if (!vis[i]) pri[++tot] = i;
for (int j=1;j<=tot&&pri[j]*i<M;j++) {
vis[i*pri[j]] = 1;
if (i%pri[j] == 0) break;
}
}
}
inline LL solve(int t, int *arr) {
for (len=1,stp=-1;len<=t*2;len<<=1,++stp);
memset(a,0,sizeof(E)*(len+9));
for (int i=0;i<=t;i++)
a[i].real() = arr[i];
for (int i=1;i<len;i++) {
pos[i] = pos[i>>1] >> 1;
if (i & 1) pos[i] |= 1 << stp;
}

fft(a, 1);
for (int i=0;i<len;i++)
a[i] *= a[i];
fft(a, -1);
LL ret = 0;
for (int i=1;i<=tot&&pri[i]<=t*2;i++)
ret += a[pri[i]].real() / len + EPS;
return ret;
}
private:
inline void fft(E *arr, int t) {
for (int i=0;i<len;i++)
if (pos[i] < i) swap(arr[pos[i]], arr[i]);
for (int k=0,gap=2;k<=stp;k++,gap<<=1) {
E wn(cos(2*PI/gap),t*sin(2*PI/gap));
for (int j=0;j<len;j+=gap) {
complex<double> cur(1, 0),t1,t2;
for (int i=j;i<j+gap/2;i++,cur*=wn) {
t1 = arr[i]; t2 = cur * arr[i+gap/2];
arr[i] = t1 + t2;
arr[i+gap/2] = t1 - t2;
}
}
}
}
}FFT;

class Node_Based_Divide_and_Conquer{
int area_size,cur_ans,root,tot;
int sum[N],vis[N],cnt[N];
public:
inline void solve() {
area_size = n; cur_ans = INF;
Get_Root(1, 1);
work(root, area_size);
}
private:
void work(int w, int sz) {
vis[w] = 1;
vout += solve(w, 0);
if (!vis[to[i]]) {
vout -= solve(to[i], 1);
area_size = sum[to[i]]<sum[w]? sum[to[i]]: sz - sum[w];
cur_ans = INF; Get_Root(to[i], w);
work(root, area_size);
}
}
}
void Get_Root(int w, int f) {
int mx = 0; sum[w] = 1;
if (to[i] != f && !vis[to[i]]) {
Get_Root(to[i], w);
sum[w] += sum[to[i]];
mx = max(mx, sum[to[i]]);
}
}
mx = max(mx, area_size - sum[w]);
if (mx < cur_ans) {
cur_ans = mx;
root = w;
}
}
LL solve(int w, int bas) {
memset(cnt,0,sizeof(int)*(tot+9));
tot = 0; Get_Dis(w, bas, w);
return FFT.solve(tot, cnt);
}
void Get_Dis(int w, int d, int f) {
cnt[d]++;
tot = max(tot, d);
if (to[i] != f && !vis[to[i]])
Get_Dis(to[i], d+1, w);
}
}NDC;

int main() {
for (int i=1;i<n;i++)
NDC.solve();
printf("%.10lf\n",(double)vout/n/(n-1));
return 0;
}


## 【Codeforces 100633D】LWDB

### Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 100000+9;
const int M = N << 1;
const int L = 20;
const int INF = 1e9;

int n,m,fa[N][L];

char c=getchar(); int f=1,ret=0;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret * f;
}

inline void Add_Edge(int u, int v, int w) {
static int T = 0;
to[++T] = v; nxt[T] = head[u]; head[u] = T; cost[T] = w;
to[++T] = u; nxt[T] = head[v]; head[v] = T; cost[T] = w;
}

void DFS(int w, int f) {
fa[w][0] = f;
dep[w] = dep[f] + 1;
if (to[i] != f) {
dis[to[i]] = dis[w] + cost[i];
DFS(to[i], w);
}
}
}

inline int DIS(int x, int y) {
int ret = dis[x] + dis[y];
if (dep[x] < dep[y]) swap(x, y);
for (int i=L-1;~i;i--)
if (dep[fa[x][i]] >= dep[y])
x = fa[x][i];
if (x == y) return ret - dis[x] * 2;
for (int i=L-1;~i;i--) {
if (fa[x][i] != fa[y][i]) {
x = fa[x][i];
y = fa[y][i];
}
}
return ret - dis[fa[x][0]] * 2;
}

class Node_Based_Divide_and_Conquer{
int cur_ans,root,area_size,rod[N][L];
int sum[N],vis[N],anc[N][L],len[N];
struct Data{
int x,y,z;
inline bool operator < (const Data &B) const {return x < B.x;}
inline bool operator <= (const Data &B) const {return x <= B.x;}
}tmp;
vector<Data> stk[N];
vector<Data>::reverse_iterator itr;
public:
inline void init() {
area_size = n; cur_ans = INF;
Get_Root(1, 1); len[root] = 1;
Build(root, n);
}
inline void modify(int w, int d, int c, int id) {
tmp.y = c; tmp.z = id;
for (int i=0,p;i<len[w];i++) {
p = anc[w][i]; tmp.x = d - rod[w][i];
if (tmp.x >= 0) {
while (!stk[p].empty() && stk[p].back() <= tmp) stk[p].pop_back();
stk[p].push_back(tmp);
}
}
}
inline int query(int w) {
Data ret={0,0,0};
for (int i=0,p;i<len[w];i++) {
p = anc[w][i]; tmp.x = rod[w][i];
itr = lower_bound(stk[p].rbegin(), stk[p].rend(), tmp);
if (itr != stk[p].rend() && ret.z < itr->z)
ret = *itr;
}
return ret.y;
}
private:
void Get_Root(int w, int f) {
int mx = 0; sum[w] = 1;
if (!vis[to[i]] && to[i] != f) {
Get_Root(to[i], w);
sum[w] += sum[to[i]];
mx = max(mx, sum[to[i]]);
}
}
mx = max(mx, area_size - sum[w]);
if (mx < cur_ans) {
cur_ans = mx;
root = w;
}
}
void Build(int w, int sz) {
vis[w] = 1; anc[w][0] = w;
if (!vis[to[i]]) {
area_size = sum[to[i]] < sum[w]? sum[to[i]]: sz - sum[w];
cur_ans = INF; Get_Root(to[i], w);
len[root] = len[w] + 1;
memcpy(anc[root]+1, anc[w], sizeof(anc[w])-4);
Build(root, area_size);
}
}
for (int i=1;i<len[w];i++)
rod[w][i] = DIS(w, anc[w][i]);
}
}NDC;

int main() {
for (int i=1,u,v;i<n;i++) {
}
DFS(1, 1);
for (int j=1;j<L;j++)
for (int i=1;i<=n;i++)
fa[i][j] = fa[fa[i][j-1]][j-1];
NDC.init();
for (int i=1,v,d,c;i<=m;i++) {
}
return 0;
}


## 【BZOJ 1095】[ZJOI2007] Hide 捉迷藏

### Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 100000+9;
const int M = N << 1;
const int INF = 1e9;

char pat[10],sta[N];

char c=getchar(); int f=1,ret=0;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret * f;
}

inline void Add_Edge(int u, int v) {
static int T = 0;
}

namespace Dynamic_Node_Decomposition{
#define DND Dynamic_Node_Decomposition
int cur,root,node_sz,cnt,in[N];
int fa[N][18],sum[N],dep[N],len[N],vis[N];
multiset<int> vout,s1[N],s2[N];
multiset<int>::iterator itr;

namespace Sparse_Table{
#define ST Sparse_Table
int _fa[N][18];

inline void init() {
for (int i=1;i<=17;i++) {
for (int j=1;j<=n;j++) {
_fa[j][i] = _fa[_fa[j][i-1]][i-1];
}
}
}

inline int query(int u, int v) {
int ret = dep[u] + dep[v];
if (dep[u] < dep[v]) swap(u, v);
for (int i=17;~i;i--) {
if (dep[_fa[u][i]] >= dep[v]) {
u = _fa[u][i];
}
}
if (u == v) return ret - dep[u] * 2;
for (int i=17;~i;i--) {
if (_fa[u][i] != _fa[v][i]) {
u = _fa[u][i];
v = _fa[v][i];
}
}
return ret - dep[_fa[u][0]] * 2;
}
};

void Get_root(int w, int f) {
sum[w] = 1; int mx = 0;
if (to[i] != f && !vis[to[i]]) {
Get_root(to[i], w);
sum[w] += sum[to[i]];
mx = max(mx, sum[to[i]]);
}
}
mx = max(mx, node_sz - sum[w]);
if (mx < cur) cur = mx, root = w;
} inline int Get_Root(int w, int SZ) {
cur = INF; node_sz = SZ;
Get_root(w,-1);
return root;
}

#define Delete(x, y) itr = x.lower_bound(y), x.erase(itr)
#define Max(x) (x.size()? itr = x.end(), *--itr : -1)
inline int Ans(multiset<int> &TMP) {
if (TMP.size() < 2) return -1;
else {
int ret = *--(itr=TMP.end());
ret += *--itr;
if (*itr <= -1) return -1;
else return ret;
}
}

inline void modify(int w, int ty) {
if (ty) cnt++; else cnt--;
for (int i=0;i<len[w];i++)
if (sta[fa[w][i]])
Delete(vout, Max(s2[fa[w][i]]));
for (int i=len[w]-2,t1,t2,dis,tmp;~i;i--) {
t1 = fa[w][i]; t2 = fa[w][i+1];
dis = ST::query(w, t2);
tmp = Max(s1[t1]);
if (tmp = (tmp <= dis)) {
Delete(vout, Ans(s2[t2]));
Delete(s2[t2], Max(s1[t1]));
}
if (!ty) Delete(s1[t1], dis);
else s1[t1].insert(dis);
if (tmp) {
s2[t2].insert(Max(s1[t1]));
vout.insert(Ans(s2[t2]));
}
}
sta[w] ^= ty >= 0;
for (int i=0;i<len[w];i++)
if (sta[fa[w][i]])
vout.insert(Max(s2[fa[w][i]]));
}

inline int query() {
if (cnt == 0) return -1;
else if (cnt == 1) return 0;
else return Max(vout);
}

void DFS(int w, int f) {
dep[w] = dep[f] + 1; ST::_fa[w][0] = f;
if (to[i] != f) DFS(to[i], w);
} void Build(int w, int sz, int sur) {
Get_Root(w,sz);
vis[w=root] = 1;
len[w] = len[sur] + 1;
fa[w][0] = root;
memcpy(fa[w]+1,fa[sur],sizeof(fa[w])-4);
if (!vis[to[i]])
Build(to[i], sum[to[i]], w);
} inline void init() {
Build(1, n, 0);
DFS(1, 1);
ST::init();
fill(sta+1, sta+1+n, 1);
for (int i=1;i<=n;i++) {
s2[fa[i][1]].insert(-1);
vout.insert(-1);
vout.insert(-1);
}
for (int i=1;i<=n;i++)
modify(i, -1);
}
};

int main() {
for (int i=1;i<n;i++)
DND::init();
for (int i=1,p;i<=m;i++) {
scanf("%s",pat+1);
if (pat[1] == 'C') {
if (sta[p]) DND::modify(p, 0);
else DND::modify(p, 1);
} else {
printf("%d\n",DND::query());
}
}
return 0;
}


## 【Codeforces 715C】Digit Tree

### Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 200000 + 9;

int n,MOD; LL vout;

char c=getchar(); int f=1,ret=0;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret * f;
}

inline void Add_Edge(int u, int v, int w) {
static int T = 0;
to[++T] = v; nxt[T] = head[u]; head[u] = T; cost[T] = w;
to[++T] = u; nxt[T] = head[v]; head[v] = T; cost[T] = w;
}

void gcd(int a, LL &x, int b, LL &y) {
if (!b) {x = 1, y = 0;}
else {gcd(b,y,a%b,x);y-=a/b*x;}
}

inline int gcd(int a, int b) {
static LL x,y;
gcd(a,x,b,y);
return (x % MOD + MOD) % MOD;
}

namespace Node_Decomposition{
#define ND Node_Decomposition
const int INF = 1e9;
int tot,node_sz,root,cur;
int sum[N],dep[N],vis[N];
map<int,int> cnt;

void Get_Root(int w, int f) {
sum[w] = 1; int mx = 0;
if (to[i] != f && !vis[to[i]]) {
Get_Root(to[i], w);
sum[w] += sum[to[i]];
mx = max(mx, sum[to[i]]);
}
}
mx = max(mx, node_sz - sum[w]);
if (mx < cur) cur = mx, root = w;
}

void DFS(int w, int f, int delta, LL p, int val) {
cnt[val] += delta;
if (!vis[to[i]] && to[i] != f) {
DFS(to[i], w, delta, p * 10 % MOD, (val + cost[i] * p) % MOD);
}
}
}

void cal(int w, int f, int t, LL val) {
vout += cnt[(-val*REV[t]%MOD+MOD)%MOD];
if (!vis[to[i]] && to[i] != f) {
cal(to[i], w, t+1, (val * 10 + cost[i]) % MOD);
}
}
}

void solve(int w, int sz) {
vis[w] = 1; cnt.clear();
if (!vis[to[i]]) {
DFS(to[i], w, 1, 10 % MOD, cost[i] % MOD);
}
}
vout += cnt[0]; cnt[0]++;
if (!vis[to[i]]) {
DFS(to[i], w, -1, 10 % MOD, cost[i] % MOD);
cal(to[i], w, 1, cost[i] % MOD);
DFS(to[i], w, 1, 10 % MOD, cost[i] % MOD);
}
}
if (!vis[to[i]]) {
node_sz = sum[to[i]] > sum[w] ? sz - sum[w] : sum[to[i]];
cur = INF; Get_Root(to[i], w);
solve(root, node_sz);
}
}
}

inline void solve() {
cur = INF; node_sz = n;
Get_Root(1,1);
solve(root,n);
}
};

int main() {
for (int i=1,u,v,w;i<n;i++) {
Add_Edge(u + 1, v + 1, w);
}
REV[0] = 1; REV[1] = gcd(10, MOD);
for (int i=2;i<=n;i++)
REV[i] = (LL)REV[i-1] * REV[1] % MOD;
ND::solve();
printf("%lld\n",vout);
return 0;
}


## 【模板库】树上点分治

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 40000 + 9;
const int M = N << 1;

int n,k,vout;

char c=getchar(); int f=1,ret=0;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret * f;
}

inline void Add_Edge(int u, int v, int w) {
static int T = 0;
to[++T] = v; nxt[T] = head[u]; head[u] = T; cost[T] = w;
to[++T] = u; nxt[T] = head[v]; head[v] = T; cost[T] = w;
}

namespace Node_Decomposition{
#define ND Node_Decomposition
const int INF = 10000000;
int vis[N],dep[N],sum[N];
int tot,cur,num_node,root;

void Get_Root(int w, int f) {
int mx = 0; sum[w] = 1;
if (to[i] != f && !vis[to[i]]) {
Get_Root(to[i], w);
mx = max(mx, sum[to[i]]);
sum[w] += sum[to[i]];
}
}
mx = max(mx, num_node - mx);
if (mx < cur) root = w, cur = mx;
}

void Get_Dep(int w, int f, int bas) {
if (to[i] != f && !vis[to[i]]) {
dep[++tot] = bas + cost[i];
Get_Dep(to[i], w, dep[tot]);
}
}
}

inline int cal(int w, int bas) {
dep[tot=1] = bas;
Get_Dep(w, w, bas);
sort(dep+1, dep+1+tot);
int r = tot, l = 1, ret = 0;
while (l < r) {
while (l < r && dep[l] + dep[r] > k) r--;
ret += r - l++;
}
return ret;
}

void solve(int w, int sz) {
vis[w] = 1;
vout += cal(w, 0);
if (!vis[to[i]]) {
vout -= cal(to[i], cost[i]);
num_node = sum[to[i]] < sum[w] ? sum[to[i]] : sz - sum[w];
cur = INF; Get_Root(to[i], w);
solve(root, num_node);
}
}
}

void solve() {
num_node = n; cur = INF;
Get_Root(1, 1);
solve(root, n);
}
};

int main() {
for (int i=1,u,v,w;i<n;i++) {
}
ND::solve();
printf("%d",vout);
return 0;
}


## 【BZOJ 1468】Tree

### Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 40000 + 9;
const int M = N << 1;
const int INF = 10000000;

int n,k,tot,cur,num_node,root,vout;

char c=getchar(); int f=1,ret=0;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret * f;
}

inline void Add_Edge(int u, int v, int w) {
static int T = 0;
to[++T] = v; nxt[T] = head[u]; head[u] = T; cost[T] = w;
to[++T] = u; nxt[T] = head[v]; head[v] = T; cost[T] = w;
}

void Get_Root(int w, int f) {
int mx = 0; sum[w] = 1;
if (to[i] != f && !vis[to[i]]) {
Get_Root(to[i], w);
mx = max(mx, sum[to[i]]);
sum[w] += sum[to[i]];
}
}
mx = max(mx, num_node - mx);
if (mx < cur) {
root = w;
cur = mx;
}
}

void Get_Dep(int w, int f, int bas) {
if (to[i] != f && !vis[to[i]]) {
dep[++tot] = bas + cost[i];
Get_Dep(to[i], w, dep[tot]);
}
}
}

inline int cal(int w, int bas) {
dep[tot=1] = bas;
Get_Dep(w, w, bas);
sort(dep+1, dep+1+tot);
int r = tot, l = 1, ret = 0;
while (l < r) {
while (l < r && dep[l] + dep[r] > k) r--;
ret += r - l++;
}
return ret;
}

void solve(int w, int sz) {
vis[w] = 1;
vout += cal(w, 0);
if (!vis[to[i]]) {
vout -= cal(to[i], cost[i]);
num_node = sum[to[i]] < sum[w] ? sum[to[i]] : sz - sum[w];
cur = INF; Get_Root(to[i], w);
solve(root, num_node);
}
}
}

int main() {