暑期专题三 树链剖分
树链剖分的实质是轻重链剖分。它利用重链和轻边均不超过\(logn\)条这样一个性质，使得其可以快速向上跳。并且它的重新编号实质上把树形结构转化为了一条条的链，也就是转化为了线性的结构，从而可以用线段树等数据结构维护相关的信息。
1.[ZJOI2008]树的统计
问题描述
一树上有\(n\)个节点，编号分别为\(1\)到\(n\)，每个节点都有一个权值\(w\)。我们将以下面的形式来要求你对这棵树完成一些操作：
CHANGE u t ：把节点\(u\)权值改为\(t\)；
QMAX u v ：询问点\(u\)到点\(v\)路径上的节点的最大权值；
QSUM u v ：询问点\(u\)到点\(v\)路径上的节点的权值和。
注意：从点\(u\)到点\(v\)路径上的节点包括\(u\)和\(v\)本身。
输入格式
第一行为一个数\(n\)，表示节点个数；
接下来\(n-1\)行，每行两个整数\(a,b\)，表示节点\(a\)与节点\(b\)之间有一条边相连；
接下来一行\(n\)个整数，第\(i\)个整数\(w_i\)表示节点\(i\)的权值；
接下来一行，为一个整数\(q\)，表示操作总数；
接下来\(q\)行，每行一个操作，以 CHANGE u t 或 QMAX u v 或 QSUM u v的形式给出。
输出格式
对于每个 QMAX 或 QSUM 的操作，每行输出一个整数表示要求的结果。
思路：树链剖分的板题，第一种操作可以转化为线段树的单点修改，第二种和第三种操作都可以转化为线段树的区间查询。
#include
using namespace std;
const int N = 200005;
const int M = 500005;
int n, w[N], tp[N], sz[N], fa[N], dep[N], son[N], maxsz, id[N], cnt;
struct node {
int to, nxt;
}e[M]; int head[N], tot;
inline void add_e(int u, int v) {e[++tot].to = v; e[tot].nxt = head[u]; head[u] = tot;}
void dfs1(int u)
{
sz[u] = 1, son[u] = 0; int maxsz = 0;
for (int i = head[u]; i; i = e[i].nxt)
{
int v = e[i].to;
if (v == fa[u]) continue;
fa[v] = u, dep[v] = dep[u] + 1;
dfs1(v);
sz[u] += sz[v];
if (sz[v] > maxsz) maxsz = sz[v], son[u] = v;
}
}
void dfs2(int u, int anc)
{
tp[u] = anc, id[u] = ++cnt;
if (son[u]) dfs2(son[u], anc);
for (int i = head[u]; i; i = e[i].nxt)
{
int v = e[i].to;
if (v == fa[u] || v == son[u]) continue;
dfs2(v, v);
}
}
int mx[N << 3], sum[N << 3];
void modify(int q, int l, int r, int x, int k)
{
if (l == r)
{
mx[q] = sum[q] = k;
return;
}
int mid = l + r >> 1;
if (x <= mid) modify(q << 1, l, mid, x, k);
else modify(q << 1 | 1, mid + 1, r, x, k);
mx[q] = max(mx[q << 1], mx[q << 1 | 1]);
sum[q] = sum[q << 1] + sum[q << 1 | 1];
}
int asksum(int q, int l, int r, int x, int y)
{
if (l >= x && r <= y) return sum[q];
int mid = l + r >> 1, ans = 0;
if (x <= mid) ans += asksum(q << 1, l, mid, x, y);
if (y > mid) ans += asksum(q << 1 | 1, mid + 1, r, x, y);
return ans;
}
int askmax(int q, int l, int r, int x, int y)
{
if (l >= x && r <= y) return mx[q];
int mid = l + r >> 1, ans = -0x3f3f3f3f;
if (x <= mid && y >= l) ans = max(ans, askmax(q << 1, l, mid, x, y));
if (y > mid && x <= r) ans = max(ans, askmax(q << 1 | 1, mid + 1, r, x, y));
return ans;
}
int querysum(int u, int v)
{
int ans = 0;
while (tp[u] ^ tp[v])
{
if (dep[tp[u]] < dep[tp[v]]) swap(u, v);
ans += asksum(1, 1, n, id[tp[u]], id[u]);
u = fa[tp[u]];
}
if (dep[u] < dep[v]) swap(u, v);
return ans + asksum(1, 1, n, id[v], id[u]);
}
int querymax(int u, int v)
{
int ans = -0x3f3f3f3f;
while (tp[u] ^ tp[v])
{
if (dep[tp[u]] < dep[tp[v]]) swap(u, v);
ans = max(ans, askmax(1, 1, n, id[tp[u]], id[u]));
u = fa[tp[u]];
}
if (dep[u] < dep[v]) swap(u, v);
return max(ans, askmax(1, 1, n, id[v], id[u]));
}
int main()
{
scanf("%d", &n);
for (int i = 1, x, y; i < n; i++) scanf("%d%d", &x, &y), add_e(x, y), add_e(y, x);
for (int i = 1; i <= n; i++) scanf("%d", &w[i]);
dfs1(1), dfs2(1, 1);
int q; scanf("%d", &q); char ch[10];
for (int i = 1; i <= n; i++) modify(1, 1, n, id[i], w[i]);
for (int i = 1, x, y; i <= q; i++)
{
scanf("%s%d%d", ch + 1, &x, &y);
if (ch[2] == 'H') modify(1, 1, n, id[x], y);
else if (ch[2] == 'M') printf("%d\n", querymax(x, y));
else printf("%d\n", querysum(x, y));
}
}
Tips:
1.千万不要把maxsz（即判断子树中的重儿子）设置成全局变量！！！切记！！！
2.若修改两点之间路径的相关信息，那么将边的信息下放到点，在修改和查询的时候，在树剖向上跳到同一条重链上时，不要修改深度最小的那个点。
2.[SDOI2011]染色
问题描述
给定一棵有\(n\)个节点的无根树和\(m\)个操作，操作有2类：
1、将节点\(a\)到节点\(b\)路径上所有点都染成颜色\(c\)；
2、询问节点\(a\)到节点\(b\)路径上的颜色段数量（连续相同颜色被认为是同一段），如“112221”由3段组成：“11”、“222”和“1”。
请你写一个程序依次完成这\(m\)个操作。
输入格式
第一行包含2个整数\(n\)和\(m\)，分别表示节点数和操作数；
第二行包含\(n\)个正整数表示\(n\)个节点的初始颜色
下面\(n-1\)行每行包含两个整数\(x\)和\(y\)，表示\(x\)和\(y\)之间有一条无向边。
下面m行每行描述一个操作：
“C a b c”表示这是一个染色操作，把节点\(a\)到节点\(b\)路径上所有点（包括\(a\)和\(b\)）都染成颜色；
“Q a b”表示这是一个询问操作，询问节点\(a\)到节点\(b\)（包括\(a\)和\(b\)）路径上的颜色段数量。
输出格式
对于每个询问操作，输出一行答案。
思路：这也是一个板题。首先仍然用树链剖分将一棵树转化为一条链，然后在线段树中维护区间左右端点的颜色，合并的时候加以处理即可。
#include
using namespace std;
struct Edge {
int to, nxt;
}e[400005]; int col[100005], dep[100005], id[100005], head[100005], tot, son[100005], sz[100005], tp[100005], fa[100005], cnt;
inline void add_e(int u, int v) {e[++tot].to = v; e[tot].nxt = head[u]; head[u] = tot;}
int sum[800005], lzy[800005], a[100005];
void Build(int q, int l, int r)
{
if (l == r) return void(sum[q] = 1);
int mid = l + r >> 1;
Build(q << 1, l, mid), Build(q << 1 | 1, mid + 1, r);
sum[q] = sum[q << 1] + sum[q << 1 | 1] - (col[mid] == col[mid + 1]);
}
void dfs1(int u)
{
int mxsz = 0; son[u] = 0, sz[u] = 1;
for (int i = head[u]; i; i = e[i].nxt)
{
int v = e[i].to;
if (v == fa[u]) continue;
fa[v] = u, dep[v] = dep[u] + 1;
dfs1(v), sz[u] += sz[v];
if (sz[v] > mxsz) mxsz = sz[v], son[u] = v;
}
}
void dfs2(int u, int anc)
{
id[u] = ++cnt, tp[u] = anc;
if (son[u]) dfs2(son[u], anc);
for (int i = head[u]; i; i = e[i].nxt)
{
int v = e[i].to;
if (v == fa[u] || v == son[u]) continue;
dfs2(v, v);
}
}
inline void pushdown(int q, int l, int r)
{
if (l == r) return;
int mid = l + r >> 1;
sum[q << 1] = sum[q << 1 | 1] = 1;
lzy[q << 1 | 1] = col[mid] = lzy[q << 1] = col[mid + 1] = lzy[q];
lzy[q] = 0;
}
void modify(int q, int l, int r, int x, int y, int k)
{
if (l >= x && r <= y)
{
sum[q] = 1;
col[l] = col[r] = lzy[q] = k;
return;
} if (lzy[q]) pushdown(q, l, r);
int mid = l + r >> 1;
if (x <= mid && y >= l) modify(q << 1, l, mid, x, y, k);
if (y > mid && x <= r) modify(q << 1 | 1, mid + 1, r, x, y, k);
sum[q] = sum[q << 1] + sum[q << 1 | 1] - (col[mid] == col[mid + 1]);
}
int query(int q, int l, int r, int x, int y)
{
if (l >= x && r <= y) return sum[q];
if (lzy[q]) pushdown(q, l, r);
int mid = l + r >> 1, ans = 0;
if (x <= mid && y >= l) ans = query(q << 1, l, mid, x, y);
if (y > mid && x <= r) ans += query(q << 1 | 1, mid + 1, r, x, y);
ans -= (x <= mid && y > mid && col[mid] == col[mid + 1]);
return ans;
}
void change(int u, int v, int k)
{
while (tp[u] ^ tp[v])
{
if (dep[tp[u]] < dep[tp[v]]) swap(u, v);
modify(1, 1, cnt, id[tp[u]], id[u], k);
u = fa[tp[u]];
} if (dep[u] > dep[v]) swap(u, v); modify(1, 1, cnt, id[u], id[v], k);
}
int ask(int u, int v)
{
int ans = 0, x = u, y = v;
while (tp[u] ^ tp[v])
{
if (dep[tp[u]] < dep[tp[v]]) swap(u, v);
ans += query(1, 1, cnt, id[tp[u]], id[u]);
u = fa[tp[u]];
} if (dep[u] > dep[v]) swap(u, v); ans += query(1, 1, cnt, id[u], id[v]);
while (tp[x] ^ tp[y])
{
if (dep[tp[x]] < dep[tp[y]]) swap(x, y);
ans -= (col[id[tp[x]]] == col[id[fa[tp[x]]]]);
x = fa[tp[x]];
} return ans;
}
char ch[5];
int main()
{
int n, m;
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
for (int i = 1, x, y; i < n; i++) scanf("%d%d", &x, &y), add_e(x, y), add_e(y, x);
dep[1] = 1, dfs1(1), dfs2(1, 1);
for (int i = 1; i <= n; i++) modify(1, 1, cnt, id[i], id[i], a[i]);
for (int i = 1, x, y, z; i <= m; i++)
{
scanf("%s%d%d", ch + 1, &x, &y);
if (ch[1] == 'Q') printf("%d\n", ask(x, y));
else scanf("%d", &z), change(x, y, z);
}
}
3.[SDOI2014] 旅行
问题描述
S国有\(N\)个城市，编号从\(1\)到\(N\)。城市间用\(N-1\)条双向道路连接，满足从一个城市出发可以到达其它所有城市。每个城市信仰不同的宗教，如飞天面条神教、隐形独角兽教、绝地教都是常见的信仰。为了方便，我们用不同的正整数代表各种宗教。
S国的居民常常旅行。旅行时他们总会走最短路，并且为了避免麻烦，只在信仰和他们相同的城市留宿。当然旅程的终点也是信仰与他相同的城市。S国政府为每个城市标定了不同的旅行评级，旅行者们常会记下途中（包括起点和终点）留宿过的城市的评级总和或最大值。
在S国的历史上常会发生以下几种事件：
? "CC x c"：城市x的居民全体改信了\(c\)教；
? "CW x w"：城市x的评级调整为\(w\)；
? "QS x y"：一位旅行者从城市\(x\)出发，到城市\(y\)，并记下了途中留宿过的城市的评级总和；
? "QM x y"：一位旅行者从城市\(x\)出发，到城市\(y\)，并记下了途中留宿过的城市的评级最大值。
由于年代久远，旅行者记下的数字已经遗失了，但记录开始之前每座城市的信仰与评级，还有事件记录本身是完好的。请根据这些信息，还原旅行者记下的数字。
为了方便，我们认为事件之间的间隔足够长，以致在任意一次旅行中，所有城市的评级和信仰保持不变。
输入格式
输入的第一行包含整数\(N,Q\)，依次表示城市数和事件数。
接下来\(N\)行，第\(i+1\)行两个整数\(W_i,C_i\)依次表示记录开始之前，城市i的评级和信仰。
接下来\(N-1\)行每行两个整数\(x,y\)表示一条双向道路。
接下来\(Q\)行，每行一个操作，格式如上所述。
输出格式
对每个QS和QM事件，输出一行，表示旅行者记下的数字。
思路：这也是一个板题。考虑每一种宗教，用线段树维护信仰这一种宗教的城市的相关信息即可。但是这样需要开十万棵线段树，时间和空间都无法承受。发现这十万棵线段树中的大部分节点都不会使用，因为最多只有\(10^5\)的规模的修改，考虑动态开点的线段树，当一个城市信仰这个宗教时再去开出相关的信息即可。
#include
using namespace std;
const int N = 2e5 + 5;
struct node {
int to, nxt;
}e[N]; int ls[N << 5], rs[N << 5], dep[N], id[N], head[N], tot, son[N], sz[N], tp[N], fa[N], cnt;
inline void add_e(int u, int v) {e[++tot].to = v; e[tot].nxt = head[u]; head[u] = tot;}
int sum[N << 5], mx[N << 5], w[N], fth[N], rt[N];
char ch[10];
void dfs1(int u)
{
son[u] = 0, sz[u] = 1; int mxsz = 0;
for (int i = head[u]; i; i = e[i].nxt)
{
int v = e[i].to;
if (v == fa[u]) continue;
fa[v] = u, dep[v] = dep[u] + 1;
dfs1(v), sz[u] += sz[v];
if (sz[v] > mxsz) mxsz = sz[v], son[u] = v;
}
}
void dfs2(int u, int anc)
{
id[u] = ++cnt, tp[u] = anc;
if (son[u]) dfs2(son[u], anc);
for (int i = head[u]; i; i = e[i].nxt)
{
int v = e[i].to;
if (v == fa[u] || v == son[u]) continue;
dfs2(v, v);
}
}
int ct;
void modify(int &q, int l, int r, int x, int k)
{
if (!q) q = ++ct;
if (l == r) return void(sum[q] = mx[q] = k);
int mid = l + r >> 1;
if (x <= mid) modify(ls[q], l, mid, x, k);
else modify(rs[q], mid + 1, r, x, k);
sum[q] = sum[ls[q]] + sum[rs[q]], mx[q] = max(mx[ls[q]], mx[rs[q]]);
}
int querysum(int q, int l, int r, int x, int y)
{
if (!q) return 0;
if (l >= x && r <= y) return sum[q];
if (l == r) return 0;
int mid = l + r >> 1, ans = 0;
if (x <= mid && y >= l) ans += querysum(ls[q], l, mid, x, y);
if (y > mid && x <= r) ans += querysum(rs[q], mid + 1, r, x, y);
return ans;
}
int querymax(int q, int l, int r, int x, int y)
{
if (!q) return 0;
if (l >= x && r <= y) return mx[q];
if (l == r) return 0;
int mid = l + r >> 1, ans = 0;
if (x <= mid && y >= l) ans = max(ans, querymax(ls[q], l, mid, x, y));
if (y > mid && x <= r) ans = max(ans, querymax(rs[q], mid + 1, r, x, y));
return ans;
}
int asksum(int u, int v)
{
int ans = 0, t = fth[u];
while (tp[u] ^ tp[v])
{
if (dep[tp[u]] < dep[tp[v]]) swap(u, v);
ans += querysum(rt[t], 1, cnt, id[tp[u]], id[u]);
u = fa[tp[u]];
}
if (dep[u] < dep[v]) swap(u, v);
return ans + querysum(rt[t], 1, cnt, id[v], id[u]);
}
int askmax(int u, int v)
{
int ans = 0, t = fth[u];
while (tp[u] ^ tp[v])
{
if (dep[tp[u]] < dep[tp[v]]) swap(u, v);
ans = max(ans, querymax(rt[t], 1, cnt, id[tp[u]], id[u]));
u = fa[tp[u]];
}
if (dep[u] < dep[v]) swap(u, v);
return max(ans, querymax(rt[t], 1, cnt, id[v], id[u]));
}
int main()
{
int n, m;
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) scanf("%d%d", &w[i], &fth[i]);
for (int i = 1, x, y; i < n; i++) scanf("%d%d", &x, &y), add_e(x, y), add_e(y, x);
dep[1] = 1, dfs1(1), dfs2(1, 1);
for (int i = 1; i <= n; i++) modify(rt[fth[i]], 1, cnt, id[i], w[i]);
for (int i = 1, x, y; i <= m; i++)
{
scanf("%s%d%d", ch + 1, &x, &y);
if (ch[2] == 'C')
{
modify(rt[fth[x]], 1, cnt, id[x], 0);
modify(rt[fth[x] = y], 1, cnt, id[x], w[x]);
}
else if (ch[2] == 'W') modify(rt[fth[x]], 1, cnt, id[x], w[x] = y);
else if (ch[2] == 'S') printf("%d\n", asksum(x, y));
else printf("%d\n", askmax(x, y));
}
}
4.NKOJ5405 魔法树
题面见：http://42.247.7.121/Content/Uploads/m1.gif
思路：相比前几道题来说，这道题需要稍动脑筋。首先将\(u\)到\(v\)路径上的点区间修改，是树链剖分的基础操作，不再赘述。那如何查询任一节点\(u\)的子树呢？手画（或观察）可以发现，树链剖分对应的NEWID其实满足dfs序的性质。这是一个相当强的性质，有了这个性质，我们可以用类似dfs序的方式，记录下一个节点的时间戳，将子树转化为区间，就可以用线段树查询了。
#include
using namespace std;
typedef long long ll;
const ll N = 2e5 + 5;
struct node {
ll to, nxt;
}e[N]; ll dep[N], id[N], ot[N], head[N], tot, son[N], sz[N], tp[N], fa[N], cnt;
inline void add_e(ll u, ll v) {e[++tot].to = v; e[tot].nxt = head[u]; head[u] = tot;}
ll lzy[N << 3], sum[N << 3], mx[N << 3], w[N], fth[N], rt[N];
char ch[10];
void dfs1(ll u)
{
son[u] = 0, sz[u] = 1; ll mxsz = 0;
for (ll i = head[u]; i; i = e[i].nxt)
{
ll v = e[i].to;
fa[v] = u, dep[v] = dep[u] + 1;
dfs1(v), sz[u] += sz[v];
if (sz[v] > mxsz) mxsz = sz[v], son[u] = v;
}
}
void dfs2(ll u, ll anc)
{
id[u] = ++cnt, tp[u] = anc;
if (son[u]) dfs2(son[u], anc);
for (ll i = head[u]; i; i = e[i].nxt)
{
ll v = e[i].to;
if (v == son[u]) continue;
dfs2(v, v);
} ot[u] = cnt;
}
inline void pushdown(ll q, ll l, ll r)
{
if (l == r) return; ll mid = l + r >> 1;
lzy[q << 1] += lzy[q], lzy[q << 1 | 1] += lzy[q];
sum[q << 1] += lzy[q] * (mid - l + 1), sum[q << 1 | 1] += lzy[q] * (r - mid);
lzy[q] = 0;
}
void modify(ll q, ll l, ll r, ll x, ll y, ll k)
{
if (l >= x && r <= y)
{
sum[q] += (r - l + 1) * k;
lzy[q] += k;
return;
}
ll mid = l + r >> 1;
if (lzy[q]) pushdown(q, l, r);
if (x <= mid && y >= l) modify(q << 1, l, mid, x, y, k);
if (y > mid && x <= r) modify(q << 1 | 1, mid + 1, r, x, y, k);
sum[q] = sum[q << 1] + sum[q << 1 | 1];
}
ll query(ll q, ll l, ll r, ll x, ll y)
{
if (l >= x && r <= y) return sum[q];
if (lzy[q]) pushdown(q, l, r);
ll mid = l + r >> 1, ans = 0;
if (x <= mid && y >= l) ans += query(q << 1, l, mid, x, y);
if (y > mid && x <= r) ans += query(q << 1 | 1, mid + 1, r, x, y);
return ans;
}
void change(ll u, ll v, ll k)
{
while (tp[u] ^ tp[v])
{
if (dep[tp[u]] < dep[tp[v]]) swap(u, v);
modify(1, 1, cnt, id[tp[u]], id[u], k);
u = fa[tp[u]];
} if (dep[u] < dep[v]) swap(u, v);
modify(1, 1, cnt, id[v], id[u], k);
}
signed main()
{
ll n; scanf("%lld", &n);
for (ll i = 1, x, y; i < n; i++) scanf("%lld%lld", &x, &y), add_e(x + 1, y + 1);
ll q; scanf("%lld", &q);
dep[1] = 1, dfs1(1), dfs2(1, 1);
for (ll i = 1, x, y, z; i <= q; i++)
{
scanf("%s", ch + 1);
if (ch[1] == 'A') scanf("%lld%lld%lld", &x, &y, &z), change(x + 1, y + 1, z);
else scanf("%lld", &x), printf("%lld\n", query(1, 1, cnt, id[x + 1], ot[x + 1]));
}
}
5.NKOJ5406 遥远的国度
问题描述
zcwwzdjn在追杀十分sb的zhx，而zhx逃入了一个遥远的国度。当zcwwzdjn准备进入遥远的国度继续追杀时，守护神RapiD阻拦了zcwwzdjn的去路，他需要zcwwzdjn完成任务后才能进入遥远的国度继续追杀。
问题是这样的：遥远的国度有\(n\)个城市，这些城市之间由一些路连接且这些城市构成了一颗树。这个国度有一个首都，我们可以把这个首都看做整棵树的根，但遥远的国度比较奇怪，首都是随时有可能变为另外一个城市的。遥远的国度的每个城市有一个防御值，有些时候RapiD会使得某两个城市之间的路径上的所有城市的防御值都变为某个值。RapiD想知道在某个时候，如果把首都看做整棵树的根的话，那么以某个城市为根的子树的所有城市的防御值最小是多少。由于RapiD无法解决这个问题，所以他拦住了zcwwzdjn希望他能帮忙。但zcwwzdjn还要追杀sb的zhx，所以这个重大的问题就被转交到了你的手上。
输入格式
第\(1\)行两个整数\(n,m\)，代表城市个数和操作数。
第\(2\)行至第\(n\)行，每行两个整数\(u,v\)，代表城市\(u\)和城市\(v\)之间有一条路。
第\(n+1\)行，有\(n\)个整数，代表所有点的初始防御值。
第\(n+2\)行一个整数\(id\)，代表初始的首都为\(id\)。
第\(n+3\)行至第\(n+m+2\)行，首先有一个整数\(opt\)，如果\(opt=1\)，接下来有一个整数\(id\)，代表把首都修改为\(id\)；如果\(opt=2\)，接下来有三个整数\(p1,p2,v\)，代表将\(p1,p2\)路径上的所有城市的防御值修改为\(v\)；如果\(opt=3\)，接下来有一个整数\(id\)，代表询问以城市\(id\)为根的子树中的最小防御值。
输出格式
对于每个\(opt=3\)的操作，输出一行代表对应子树的最小点权值。
思路：子树的话跟上道题类似的处理方式。这个题主要的考点是换根。我们采取跟dfs序类似的换根操作，分三种情况讨论。
先以\(1\)为根dfs一遍建树，然后设询问的点为x，
1.x与根是一个点，此时显然子树就是整棵树。
2.根在x的子树中，设y是x的儿子且y是根的祖先，子树就是除y的子树以外的所有点。寻找的话可以用重链剖分来寻找（对于这个题也可以直接暴力枚举x的儿子，因为数据强度较低）。
3.对于所有不适用于前两种的情况，x的子树就是在原树中x的子树，这是显然的。
这样我们就处理完了换根，剩下的就是套模板了。
#include
using namespace std;
typedef long long ll;
const ll N = 2e5 + 5;
struct node {
ll to, nxt;
}e[N]; ll dep[N], id[N], ot[N], head[N], tot, son[N], sz[N], tp[N], fa[N], cnt;
inline void add_e(ll u, ll v) {e[++tot].to = v; e[tot].nxt = head[u]; head[u] = tot;}
ll lzy[N << 3], mn[N << 3], mx[N << 3], w[N], fth[N], rt[N];
char ch[10];
void dfs1(ll u)
{
son[u] = 0, sz[u] = 1; ll mxsz = 0;
for (ll i = head[u]; i; i = e[i].nxt)
{
ll v = e[i].to;
if (v == fa[u]) continue;
fa[v] = u, dep[v] = dep[u] + 1;
dfs1(v), sz[u] += sz[v];
if (sz[v] > mxsz) mxsz = sz[v], son[u] = v;
}
}
void dfs2(ll u, ll anc)
{
id[u] = ++cnt, tp[u] = anc;
if (son[u]) dfs2(son[u], anc);
for (ll i = head[u]; i; i = e[i].nxt)
{
ll v = e[i].to;
if (v == fa[u] || v == son[u]) continue;
dfs2(v, v);
} ot[u] = cnt;
}
inline void pushdown(ll q, ll l, ll r)
{
if (l == r) return;
lzy[q << 1] = lzy[q << 1 | 1] = mn[q << 1] = mn[q << 1 | 1] = lzy[q];
lzy[q] = 0;
}
void modify(ll q, ll l, ll r, ll x, ll y, ll k)
{
if (l >= x && r <= y) return void(mn[q] = lzy[q] = k);
ll mid = l + r >> 1;
if (lzy[q]) pushdown(q, l, r);
if (x <= mid && y >= l) modify(q << 1, l, mid, x, y, k);
if (y > mid && x <= r) modify(q << 1 | 1, mid + 1, r, x, y, k);
mn[q] = min(mn[q << 1], mn[q << 1 | 1]);
}
ll query(ll q, ll l, ll r, ll x, ll y)
{
if (l >= x && r <= y) return mn[q];
if (lzy[q]) pushdown(q, l, r);
ll mid = l + r >> 1, ans = 0x3f3f3f3f3f3f3f3f;
if (x <= mid && y >= l) ans = min(ans, query(q << 1, l, mid, x, y));
if (y > mid && x <= r) ans = min(ans, query(q << 1 | 1, mid + 1, r, x, y));
return ans;
}
void change(ll u, ll v, ll k)
{
while (tp[u] ^ tp[v])
{
if (dep[tp[u]] < dep[tp[v]]) swap(u, v);
modify(1, 1, cnt, id[tp[u]], id[u], k);
u = fa[tp[u]];
} if (id[u] < id[v]) swap(u, v);
modify(1, 1, cnt, id[v], id[u], k);
}
inline ll Go_up(ll u, ll v)
{
while (tp[u] ^ tp[v])
{
if (dep[tp[u]] < dep[tp[v]]) swap(u, v);
if (fa[tp[u]] == v) return tp[u];
u = fa[tp[u]];
} if (dep[u] > dep[v]) swap(u, v);
return son[u];
}
signed main()
{
memset(mn, 0x3f, sizeof mn); ll qes = 0;
ll n, m, cpt; scanf("%lld%lld", &n, &m);
for (ll i = 1, x, y; i < n; i++) scanf("%lld%lld", &x, &y), add_e(x, y), add_e(y, x);
dep[1] = 1, dfs1(1), dfs2(1, 1);
for (ll i = 1, x; i <= n; i++) scanf("%lld", &x), modify(1, 1, cnt, id[i], id[i], x);
scanf("%lld", &cpt);
for (ll i = 1, op, x, y, z; i <= m; i++)
{
scanf("%lld", &op);
if (op == 1) scanf("%lld", &cpt);
else if (op == 2) scanf("%lld%lld%lld", &x, &y, &z), change(x, y, z);
else
{
scanf("%lld", &x);
if (x == cpt) printf("%lld\n", query(1, 1, cnt, 1, cnt));
else if (id[x] < id[cpt] && id[cpt] <= ot[x])
{
ll y = Go_up(cpt, x);
printf("%lld\n", min(query(1, 1, cnt, 1, id[y] - 1), query(1, 1, cnt, ot[y] + 1, cnt)));
} else printf("%lld\n", query(1, 1, cnt, id[x], ot[x]));
}
}
}
6.[Ynoi2017][NKOJ5404][Luogu5354]由乃的OJ
问题描述
由乃正在做她的OJ。现在她在处理OJ上的用户排名问题。OJ上注册了\(n\)个用户，编号为\(1～n\)，一开始他们按照编号
排名。由乃会按照心情对这些用户做以下四种操作，修改用户的排名和编号：然而由乃心情非常不好，因为Deus天
天问她题。。。因为Deus天天问由乃OI题，所以由乃去学习了一下OI，由于由乃智商挺高，所以OI学的特别熟练她
在RBOI2016中以第一名的成绩进入省队，参加了NOI2016获得了金牌保送
Deus：这个题怎么做呀？
yuno：这个不是NOI2014的水题吗。。。
Deus：那如果出到树上，多组链询问，带修改呢？
yuno：诶。。。？？？
Deus：这题叫做睡觉困难综合征哟~
虽然由乃OI很好，但是她基本上不会DS，线段树都只会口胡，比如她NOI2016的分数就是\(100+100+100+0+100+100。
。。\)NOIP2017的分数是\(100+0+100+100+0+100\)所以她还是只能找你帮她做了。。。
给你一个有\(n\)个点的树，每个点的包括一个位运算\(opt\)和一个权值\(x\)，位运算有&,l,^三种，分别用1,2,3表示。
每次询问包含三个数\(x,y,z\),初始选定一个数\(v\)。然后\(v\)依次经过从\(x\)到\(y\)的所有节点，每经过一个点\(i\)，\(v\)就变成\(v\) \(opt_i\)
\(x_i\)，所以他想问你，最后到\(y\)时，希望得到的值尽可能大，求最大值？给定的初始值\(v\)必须是在\([0,z]\)之间。每次修
改包含三个数\(x,y,z\)，意思是把\(x\)点的操作修改为\(y\)，数值改为\(z\)
输入格式
第一行三个数\(n，m，k\)。\(k\)的意义是每个点上的数，以及询问中的数值\(z\)都小于\(2^k\)。之后\(n\)行
每行两个数\(x,y\)表示该点的位运算编号以及数值
之后\(n-1\)行，每行两个数\(x,y\)表示\(x\)和\(y\)之间有边相连
之后\(m\)行，每行四个数，\(Q,x,y,z\)表示这次操作为\(Q\)(\(1\)为询问，\(2\)为修改)，\(x，y，z\)意义如题所述
\(0 \leq n , m \leq 100000\) , \(k \leq 64\)
输出格式
对于每个操作\(1\)，输出到最后可以造成的最大刺激度\(v\)
思路：相比于前几道题，这道题的难度相对来说就要大上许多。首先，这个位运算它是没有交换律和结合律的，所以它只能强行合并。
首先，先考虑每一位的位运算，在线段树上维护\(l_0,l_1,r_0,r_1\)四个信息，分别表示当第\(i\)位是\(0/1/0/1\)，从左/左/右/右边进入时得到的值，目的就是通过合并区间来模拟从\(x\)到\(y\)的过程。
那么合并的方式就非常简单了。设\(x\)是\(y\)和\(z\)合并的之后的区间，有如下四个公式来合并：
\(x.l_0[i]\) \(=\) \((y.l_0[i]\)&&\(z.l_1[i])\) \(||\) \((!y.l_0[i]\)&&\(z.l_0[i])\)
\(x.l_1[i]\) \(=\) \((y.l_1[i]\)&&\(z.l_1[i])\) \(||\) \((!y.l_1[i]\)&&\(z.l_0[i])\)
\(x.r_0[i]\) \(=\) \((y.r_1[i]\)&&\(z.r_0[i])\) \(||\) \((y.r_0[i]\)&&\(!z.r_0[i])\)
\(x.r_1[i]\) \(=\) \((y.r_1[i]\)&&\(z.r_1[i])\) \(||\) \((y.r_0[i]\)&&\(!z.r_1[i])\)。
这样的话，我们可以通过维护线段树来得到一个区间，它代表从\(x\)到\(y\)的路径中，你在第\(i\)位中放一个\(0/1\)，最终会得到什么。
那么在得到这个区间之后，我们怎么去求最大值呢？考虑贪心，尽可能让高位操作之后的结果变成\(1\)，那么从高位到低位逐位考虑。对于每一位来说，有一下几种情况：
1.如果放一个\(0\)进去变成了\(1\)，直接放\(0\)最优。
2.如果放一个\(1\)进去还是\(1\)（\(0\)放进去是\(0\)），且当前的条件允许放\(1\)，就放\(1\)。
3.如果无论放什么进去，出来的都不是\(1\)，那么放\(0\)。
时间复杂度\(O(nklognlogn)\)，有点大，无法通过本题。
怎么办呢？这个时间复杂度中两个\(log\)是树剖本身自带的复杂度，不好优化，那么想想能否将\(k\)这个\(64\)优化掉。考虑到位运算每一位的运算是互不影响的，于是用想到用\(unsigned\) \(long\) \(long\)来把这64棵线段树合并为一棵线段树。这样，时间复杂度优化为\(O(nlognlogn)\)，可以通过本题。
#include
using namespace std;
typedef unsigned long long ull;
const ull N = 1e5 + 5;
const ull maxx = -1ull;
struct Edge {
ull to, nxt;
}e[N << 1]; ull head[N], tot, son[N], id[N], fa[N], sz[N], dep[N], tp[N], cnt;
inline void add_e(ull u, ull v) {e[++tot].to = v; e[tot].nxt = head[u]; head[u] = tot;}
ull opt[N], w[N];
void dfs1(ull u)
{
ull mxsz = 0; son[u] = 0, sz[u] = 1;
for (int i = head[u]; i; i = e[i].nxt)
{
ull v = e[i].to;
if (v == fa[u]) continue;
fa[v] = u, dep[v] = dep[u] + 1;
dfs1(v), sz[u] += sz[v];
if (mxsz < sz[v]) mxsz = sz[v], son[u] = v;
}
}
void dfs2(ull u, ull anc)
{
id[u] = ++cnt, tp[u] = anc;
if (son[u]) dfs2(son[u], anc);
for (int i = head[u]; i; i = e[i].nxt)
{
ull v = e[i].to;
if (v == fa[u] || v == son[u]) continue;
dfs2(v, v);
}
}
struct node {
ull a[2][2];
}ans[N << 4];
node merge(node x, node y)
{
node as;
as.a[0][0] = (x.a[0][0] & y.a[1][0]) | (~x.a[0][0] & y.a[0][0]);
as.a[1][0] = (x.a[1][0] & y.a[1][0]) | (~x.a[1][0] & y.a[0][0]);
as.a[0][1] = (x.a[1][1] & y.a[0][1]) | (~y.a[0][1] & x.a[0][1]);
as.a[1][1] = (x.a[1][1] & y.a[1][1]) | (~y.a[1][1] & x.a[0][1]);
return as;
}
void modify(ull q, ull l, ull r, ull x, ull k, ull op)
{
if (l == r)
{
if (op == 1)
{
ans[q].a[0][0] = ans[q].a[0][1] = (k & 0);
ans[q].a[1][0] = ans[q].a[1][1] = (k & maxx);
}
else if (op == 2)
{
ans[q].a[0][0] = ans[q].a[0][1] = (k | 0);
ans[q].a[1][0] = ans[q].a[1][1] = (k | maxx);
}
else
{
ans[q].a[0][0] = ans[q].a[0][1] = (k ^ 0);
ans[q].a[1][0] = ans[q].a[1][1] = (k ^ maxx);
} return;
}
ull mid = l + r >> 1;
if (x <= mid) modify(q << 1, l, mid, x, k, op);
else modify(q << 1 | 1, mid + 1, r, x, k, op);
ans[q] = merge(ans[q << 1], ans[q << 1 | 1]);
}
node query(ull q, ull l, ull r, ull x, ull y)
{
if (l >= x && r <= y) return ans[q];
ull mid = l + r >> 1;
if (x <= mid && y >= l)
{
node res = query(q << 1, l, mid, x, y);
if (y > mid && x <= r) res = merge(res, query(q << 1 | 1, mid + 1, r, x, y));
return res;
} else return query(q << 1 | 1, mid + 1, r, x, y);
}
node ans1[N], ans2[N];
int cnt1, cnt2;
ull gett(ull x, ull y, ull z)
{
cnt1 = cnt2 = 0;
while (tp[x] ^ tp[y])
{
if (dep[tp[x]] >= dep[tp[y]]) ans1[++cnt1] = query(1, 1, cnt, id[tp[x]], id[x]), x = fa[tp[x]];
else ans2[++cnt2] = query(1, 1, cnt, id[tp[y]], id[y]), y = fa[tp[y]];
} if (id[x] > id[y]) ans1[++cnt1] = query(1, 1, cnt, id[y], id[x]);
else ans2[++cnt2] = query(1, 1, cnt, id[x], id[y]);
for (int i = 1; i <= cnt1; i++) swap(ans1[i].a[0][0], ans1[i].a[0][1]), swap(ans1[i].a[1][0], ans1[i].a[1][1]);
node res;
if (cnt1)
{
res = ans1[1];
for (int i = 2; i <= cnt1; i++) res = merge(res, ans1[i]);
if (cnt2) res = merge(res, ans2[cnt2]);
} else res = ans2[cnt2]; ull ans = 0;
for (int i = cnt2 - 1; i >= 1; i--) res = merge(res, ans2[i]);
for (int i = 63; ~i; i--)
{
ull t0 = (res.a[0][0] >> i) & 1ull, t1 = (res.a[1][0] >> i) & 1ull;
if (t0 >= t1 || (1ull << i) > z) ans |= (t0 ? (1ull << i) : 0);
else z -= (1ull << i), ans |= (1ull << i);
} return ans;
}
signed main()
{
ull n, m, k;
scanf("%llu%llu%llu", &n, &m, &k);
for (int i = 1; i <= n; i++) scanf("%llu%llu", &opt[i], &w[i]);
for (int i = 1, x, y; i < n; i++) scanf("%d%d", &x, &y), add_e(x, y), add_e(y, x);
dep[1] = 1, dfs1(1), dfs2(1, 1);
for (int i = 1; i <= n; i++) modify(1, 1, cnt, id[i], w[i], opt[i]);
for (ull i = 1, op, x, y, z; i <= m; i++)
{
scanf("%llu%llu%llu%llu", &op, &x, &y, &z);
if (op == 2) modify(1, 1, cnt, id[x], z, y);
else printf("%llu\n", gett(x, y, z));
}
}
7.NKOJ4573 Falsita
问题描述
到海边了呢......
如果没有那次选择,现在是不是会好些呢......
都过去了。
仰望着星空,迎面吹过一阵阵海风,倚靠着护栏,Fine 在海边静静地伫立着,在一个个无际的长夜后,Fine 终于放下了往事的痛楚,得到了治愈。
但是作为 Fine 的另一重人格的 Falsita 就没那么幸运了。她仍然被各种繁忙的事务困扰着。
虽然同在一副躯体中,Fine 与 Falsita 的精神世界却相差甚远,Fine 可以轻易地构造出幻梦时,Falsita 却只能停留在现实的痛楚中。
但是为了生活需要,她们还是需要经常达成共识。
让我们形式化的描述一下吧。
她们所在的精神世界是一棵以\(1\)号节点为根的树,每个树上的节点\(u\)都有一个权值\(W_u\),她们每个人分别都在一个节点上,达成共识的方法就是两个人都到达一个共识节点(即到达它们的最近公共祖先)。
一个点\(u\)与另外一个点\(v\)之间想要达到共识需要花费的代价为\(W_u+W_v\)。
有时两人的精神有所触动时,有时点的权值会改变成某个数,有时以某个点的子树中的所有点的权值会加上某个数。
Falsita 和 Fine 经常需要达成共识,每一次询问,已知达成的共识节点,求她们花费的期望代价。
输入格式
输入共\(m+3\)行。
第一行两个整数\(n,m\),表示节点个数和操作数。
第二行\(n-1\)个整数\(P_i\),表示节点\(i(i=2,...,n)\)的父亲节点的编号。
第三行\(n\)个整数\(W_i\)。
接下来\(m\)行,每行表示一个操作。
1.S u delta表示将节点\(u\)的权值加上\(delta\)。
2.M u delta表示将以节点\(u\)为根的子树中的所有节点的权值加上\(delta\)。
3.Q u表示询问共识节点为\(u\)时的答案。
询问保证\(u\)不是叶子节点。
输出格式
对于每组询问,输出答案,答案精确到小数点后\(6\)位。
你的程序输出的答案需要与标准答案之差不超过\(10^{-5}\)。
思路：这道题的难度相对上一道题差不多，这也是难度不小的一道题。
先考虑第一种操作带来的贡献。（先鸽了）
#include
using namespace std;
typedef long long ll;
const ll N = 3e5 + 5;
struct Edge {
ll to, nxt;
}e[N << 1]; ll head[N], tot, cnt, num[N], w[N], num1[N], tp[N], dep[N], id[N], sz[N], val[N], fa[N], son[N], ou[N], lzy[N << 3][2], sum[N << 3];
inline void add_e(ll u, ll v) {e[++tot].to = v; e[tot].nxt = head[u]; head[u] = tot;}
void dfs1(ll u)
{
son[u] = 0, sz[u] = 1; ll mxsz = 0;
for (ll i = head[u]; i; i = e[i].nxt)
{
ll v = e[i].to;
dep[v] = dep[u] + 1;
dfs1(v), sz[u] += sz[v], val[u] += val[v];
if (mxsz < sz[v]) mxsz = sz[v], son[u] = v;
} ll tmp = sz[u];
for (ll i = head[u]; i; i = e[i].nxt)
{
ll v = e[i].to;
num[u] += val[v] * (sz[u] - sz[v]), num1[u] += sz[v] * (tmp - sz[v]);
tmp -= sz[v];
} num[u] += (sz[u] - 1) * w[u];
}
void dfs2(ll u, ll anc)
{
id[u] = ++cnt, tp[u] = anc;
if (!son[u]) return void(ou[u] = cnt);
if (son[u]) dfs2(son[u], anc);
for (ll i = head[u]; i; i = e[i].nxt)
{
ll v = e[i].to;
if (v == son[u]) continue;
dfs2(v, v);
} ou[u] = cnt;
}
void pushdown(ll q, ll l, ll r, ll op)
{
if (l == r) return;
lzy[q << 1][op] += lzy[q][op], lzy[q << 1 | 1][op] += lzy[q][op];
lzy[q][op] = 0;
}
void modify(ll q, ll l, ll r, ll x, ll y, ll k, ll op)
{
if (l >= x && r <= y) return void(lzy[q][op] += k);
if (lzy[q][op]) pushdown(q, l, r, op);
ll mid = l + r >> 1;
if (x <= mid && y >= l) modify(q << 1, l, mid, x, y, k, op);
if (y > mid && x <= r) modify(q << 1 | 1, mid + 1, r, x, y, k, op);
}
ll query(ll q, ll l, ll r, ll x, ll y)
{
if (l == r) return lzy[q][0] * (sz[y] - sz[son[y]]) + lzy[q][1] * num1[y];
ll mid = l + r >> 1, ans = 0;
if (lzy[q][0]) pushdown(q, l, r, 0);
if (lzy[q][1]) pushdown(q, l, r, 1);
if (x <= mid) return query(q << 1, l, mid, x, y);
else return query(q << 1 | 1, mid + 1, r, x, y);
}
void update(ll x, ll k)
{
while (tp[x] ^ tp[1])
{
modify(1, 1, cnt, id[tp[x]], id[fa[x]], k, 0);
num[fa[tp[x]]] += (sz[fa[tp[x]]] - sz[tp[x]]) * k;
x = fa[tp[x]];
} x = fa[x];
if (x) return void(modify(1, 1, cnt, id[1], id[x], k, 0));
}
signed main()
{
ll n, m;
scanf("%lld%lld", &n, &m);
for (ll i = 2; i <= n; i++) scanf("%lld", &fa[i]), add_e(fa[i], i);
for (ll i = 1; i <= n; i++) scanf("%lld", &val[i]), w[i] = val[i];
dep[1] = 1, dfs1(1), dfs2(1, 1); char ch[10];
for (ll i = 1, x, y, z; i <= m; i++)
{
scanf("%s", ch + 1);
if (ch[1] == 'S')
{
scanf("%lld%lld", &x, &y);
num[x] += (sz[x] - 1) * y;
update(x, y);
}
else if (ch[1] == 'M')
{
scanf("%lld%lld", &x, &y);
modify(1, 1, cnt, id[x], ou[x], 2 * y, 1);
update(x, y * sz[x]);
}
else scanf("%lld", &x), printf("%.6lf\n", 1.0 * (query(1, 1, cnt, id[x], x) + num[x]) / num1[x]);
}
}