## 【BZOJ 3924】[ZJOI2015] 幻想乡战略游戏

### 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 = 18;
const int INF = 1e9;

int n,m,head[N],nxt[M],to[M],cost[M];

inline int read() {
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 c) {
static int T = 0;
to[++T] = v; nxt[T] = head[u]; head[u] = T; cost[T] = c;
to[++T] = u; nxt[T] = head[v]; head[v] = T; cost[T] = c;
}

class Heavy_Light_Decomposition{
int dep[N],dis[N],fa[N],top[N],sz[N];
int go[N],pos[N],len[N],sum,cnt;
vector<int> que[N];
class Fenwick_Tree{
#define lowbit(x) ((x)&-(x))
int arr[N];
public:
inline void modify(int l, int r, int delta) {
modify(l-1, -delta);
modify(r, delta);
}
inline int query(int p) {
LL ret = 0;
for (int i=p;i<=n;i+=lowbit(i))
ret += arr[i];
return ret;
}
private:
inline void modify(int p, int delta) {
for (int i=p;i;i-=lowbit(i))
arr[i] += delta;
}
}BIT;
public:
inline void init() {
DFS1(1, 1);
DFS2(1, 1, 1);
}
inline int DIS(int u, int v) {
int lca = LCA(u, v);
return dis[u] + dis[v] - (dis[lca] << 1);
}
inline void modify(int w, int v) {
sum += v;
for (;w;w=fa[top[w]])
BIT.modify(pos[top[w]], pos[w], v);
}
inline int query() {
int w = 1, tag = 1;
while (tag) {
int l = 1, r = len[w]-1, mid, ret = 0;
while (l <= r) {
mid = l + r >> 1;
if (BIT.query(pos[que[w][mid]])*2 <= sum) r = mid - 1;
else l = mid + 1, ret = mid;
}
w = que[w][ret]; tag = 0;
for (int i=head[w];i;i=nxt[i]) {
if (dep[to[i]] > dep[w] && BIT.query(pos[to[i]])*2 > sum) {
tag = 1; w = to[i]; break;
}
}
}
return w;
}
private:
void DFS1(int w, int f) {
sz[w] = 1; dep[w] = dep[f] + 1;
for (int i=head[w];i;i=nxt[i]) {
if (to[i] != f) {
dis[to[i]] = dis[w] + cost[i];
fa[to[i]] = w;
DFS1(to[i], w);
sz[w] += sz[to[i]];
if (sz[to[i]] > sz[go[w]])
go[w] = to[i];
}
}
}
void DFS2(int w, int f, int t) {
que[t].push_back(w);
top[w] = t;	pos[w] = ++cnt;
if (go[w]) DFS2(go[w], w, t);
for (int i=head[w];i;i=nxt[i]) {
if (to[i] != f && to[i] != go[w]) {
DFS2(to[i], w, to[i]);
}
}
len[w] = que[w].size();
que[w].push_back(w);
}
inline int LCA(int u, int v) {
while (top[u] != top[v])
if (dep[top[u]] > dep[top[v]]) u = fa[top[u]];
else v = fa[top[v]];
return dep[u] > dep[v]? v: u;
}
}HLD;

class Vertex_Based_Divide_and_Conquer{
int sum[N],vis[N],len[N],fa[N][L],rod[N][L];
int root,size,cur,val_sum[N],val_sum_del[N];
LL part_ans[N],part_ans_del[N];
public:
inline void init() {
int rt = Get_Root(1, n);
len[rt] = 1;
build(rt, n);
}
inline void modify(int w, int v) {
val_sum[w] += v;
for (int i=1,p=w,d,u;i<len[w];i++) {
u = p; p = fa[w][i]; d = rod[w][i];
val_sum[p] += v;
val_sum_del[u] += v;
part_ans[p] += (LL)v * d;
part_ans_del[u] += (LL)v * d;
}
}
inline LL query(int w) {
LL ret = part_ans[w];
for (int i=1,p=w,u,d;i<len[w];i++) {
u = p; p = fa[w][i]; d = rod[w][i];
ret += part_ans[p] + (LL)val_sum[p] * d;
ret -= part_ans_del[u] + (LL)val_sum_del[u] * d;
}
return ret;
}
private:
inline int Get_Root(int w, int sz) {
size = sz; cur = INF;
Get_root(w, w);
return root;
}
void Get_root(int w, int f) {
int mx = 1; sum[w] = 1;
for (int i=head[w];i;i=nxt[i]) {
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, size - sum[w]);
if (mx < cur) cur = mx, root = w;
}
void build(int w, int sz) {
vis[w] = 1; fa[w][0] = w;
for (int i=1;i<len[w];i++)
rod[w][i] = HLD.DIS(w, fa[w][i]);
for (int i=head[w],tmp,rt;i;i=nxt[i]) {
if (!vis[to[i]]) {
tmp = sum[to[i]]<sum[w]? sum[to[i]]: sz-sum[w];
rt = Get_Root(to[i], tmp);
len[rt] = len[w] + 1;
memcpy(fa[rt]+1, fa[w], sizeof(int)*len[w]);
build(rt, tmp);
}
}
}

}VDC;

int main() {
n = read(); m = read();
for (int i=1,u,v;i<n;i++) {
u = read(); v = read();
Add_Edge(u, v, read());
}
HLD.init();
VDC.init();
for (int i=1,p,v;i<=m;i++) {
p = read(); v = read();
HLD.modify(p, v);
VDC.modify(p, v);
p = HLD.query();
printf("%lld\n",VDC.query(p));
}
return 0;
}


## 【HDU 5571】tree

### Code

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

const int N = 30000+9;
const int M = N << 1;
const int L = 16;
const int INF = 1e9;

int n,m,T,head[N],to[M],nxt[M],cost[M],ori[N];
int val[N],dep[N],dis[N],fa[N][L],P[N],V[N];
LL ans[N];

inline void Add_Edge(int u, int v, int w) {
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;
}

inline int read() {
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;
}

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

inline int LCA(int u, int v) {
if (dep[u] < dep[v]) swap(u, v);
for (int i=L-1;~i;i--) {
if (dep[fa[u][i]] >= dep[v]) {
u = fa[u][i];
}
}
if (u == v) return u;
for (int i=L-1;~i;i--) {
if (fa[u][i] != fa[v][i]) {
u = fa[u][i];
v = fa[v][i];
}
}
return fa[u][0];
}

inline int DIS(int u, int v) {
int lca = LCA(u, v);
return dis[u] + dis[v] - dis[lca] * 2;
}

class Node_Based_Divide_and_Conquer{
int area_sz,cur_ans,root,rod[N][L],sum[N];
int anc[N][L],len[N],tos[2][N],tot[2][N];
bool vis[N]; LL f[2][N],sub[2][N];

public:
inline void init() {
memset(vis,0,sizeof(vis));
cur_ans = INF; area_sz = n;
Get_Root(1, 1); len[root] = 1;
Build(root, n);
}

inline void prework() {
memset(f, 0 ,sizeof(f));
memset(sub, 0, sizeof(sub));
memset(tot, 0, sizeof(tot));
memset(tos, 0, sizeof(tos));
}

inline void modify(int w, int t, int p) {
for (int i=0,pre,cur;i<len[w];i++) {
cur = anc[w][i];
f[t][cur] += rod[w][i] * p;
tot[t][cur] += p;
if (i) {
pre = anc[w][i-1];
sub[t][pre] += rod[w][i] * p;
tos[t][pre] += p;
}
}
}

inline LL query(int w, int t, int k) {
LL ret = 0,s,d; t ^= 1;
ret += f[t][w] << k;
for (int i=1,cur,pre;i<len[w];i++) {
cur = anc[w][i]; pre = anc[w][i-1];
d = f[t][cur] - sub[t][pre];
s = tot[t][cur] - tos[t][pre];
ret += d + s * rod[w][i] << k;
}
return ret;
}
private:
void Get_Root(int w, int F) {
sum[w] = 1; int mx = 0;
for (int i=head[w];i;i=nxt[i]) {
if (!vis[to[i]] && to[i] != F) {
Get_Root(to[i], w);
mx = max(sum[to[i]], mx);
sum[w] += sum[to[i]];
}
}
mx = max(mx, area_sz - sum[w]);
if (mx < cur_ans) {
cur_ans = mx;
root = w;
}
}

void Build(int w, int sz) {
vis[w] = 1;
anc[w][0] = w;
for (int i=head[w];i;i=nxt[i]) {
if (!vis[to[i]]) {
area_sz = 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(int)*len[w]);
Build(root, area_sz);
}
}
for (int i=0;i<len[w];i++)
rod[w][i] = DIS(w, anc[w][i]);
}
}NDC;

int main() {
for (LL vout=0;~scanf("%d",&n);vout=T=0) {
memset(head,0,sizeof(head));
memset(ans,0,sizeof(ans));
for (int i=1;i<=n;i++)
ori[i] = read();
for (int i=1,u,v,w;i<n;i++) {
u = read(); v = read(); w = read();
Add_Edge(u, v, w);
}
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();
m = read();
for (int i=1;i<=m;i++) {
P[i] = read();
V[i] = read();
}
for (int j=0;j<L;j++,vout=0) {
memcpy(val,ori,sizeof(ori));
NDC.prework();
for (int i=1;i<=n;i++) {
val[i] >>= j; val[i] &= 1;
NDC.modify(i, val[i], 1);
vout += NDC.query(i, val[i], j);
}
for (int i=1,p,v;i<=m;i++) {
p = P[i]; v = (V[i] >> j) & 1;
vout -= NDC.query(p, val[p], j);
NDC.modify(p, val[p], -1);
NDC.modify(p, v, 1);
vout += NDC.query(p, val[p] = v, j);
ans[i] += vout;
}
}
for (int i=1;i<=m;i++)
printf("%I64d\n",ans[i]);
}
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 head[N],to[M],nxt[M],cost[M],dis[N],dep[N];
int n,m,fa[N][L];

inline int read() {
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;
for (int i=head[w];i;i=nxt[i]) {
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;
for  (int i=head[w];i;i=nxt[i]) {
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;
for (int i=head[w];i;i=nxt[i]) {
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() {
n = read();
for (int i=1,u,v;i<n;i++) {
u = read(); v = read();
Add_Edge(u, v, read());
}
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();
m = read();
for (int i=1,v,d,c;i<=m;i++) {
if (read() == 1) {
v = read(); d = read();
NDC.modify(v, d, read(), i);
} else printf("%d\n",NDC.query(read()));
}
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;

int head[N],to[M],nxt[M],n,m;
char pat[10],sta[N];

inline int read() {
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;
to[++T] = v; nxt[T] = head[u]; head[u] = T;
to[++T] = u; nxt[T] = head[v]; head[v] = T;
}

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;
for (int i=head[w];i;i=nxt[i]) {
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;
for (int i=head[w];i;i=nxt[i])
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);
for (int i=head[w];i;i=nxt[i])
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() {
n = read();
for (int i=1;i<n;i++)
Add_Edge(read(), read());
DND::init();
m = read();
for (int i=1,p;i<=m;i++) {
scanf("%s",pat+1);
if (pat[1] == 'C') {
p = read();
if (sta[p]) DND::modify(p, 0);
else DND::modify(p, 1);
} else {
printf("%d\n",DND::query());
}
}
return 0;
}