【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 , c i ≤ 1 0 5 N,Q,c_i\le10^5 N,Q,ci​≤105

思路

简单的树剖线段树，只不过颜色太多，要动态开点，最后线段树节点个数才是 $O(n\log n)$ 的。

明明这么模板我却写不出来，下面是我的 fake 思路：离线，把在任意时刻可能为某种颜色的点建一棵树，然后树剖。然后太难写了我写了 100 多行卡住了 qwq 。然后重写了 qwq 。

就算是平常自己写题也要养成先把细节想清楚再写的习惯，考场上更加，码量大了时间浪费不起。

p.s. 后来写树剖还写错了 WA 了一发，记录一下：树剖要先跳 dpt[top[x]] 比较深的，而不是 dpt[x] 比较深的点，随便出个数据就插掉了。

p.p.s.我也太菜了吧，树剖都不会写。我记得我上次写树剖（好久以前）的时候把 dfs 写错了 qwq 。

代码

#include
using namespace std;
const int N = 1e5 + 10, M = N << 1, E = 20;
namespace Graph
{int h[N], ecnt, nxt[M], v[M];void clear(){ecnt = 1;}void add_dir(int _u, int _v){v[++ecnt] = _v;nxt[ecnt] = h[_u]; h[_u] = ecnt;}void add_undir(int _u, int _v){add_dir(_u, _v);add_dir(_v, _u);}
}
using namespace Graph;
int n, q, m, w[N], c[N];
int faz[N], siz[N], son[N], dpt[N], top[N], dfn[N], rfn[N], idx;
int ch[N*E][2], tcnt, root[N];
struct node{int tmax, tsum;node(){}node(int x){tmax = tsum = x;}node(int x, int y){tmax = x; tsum = y;}node operator + (node u){return node(max(tmax, u.tmax), tsum+u.tsum);}
}t[N*E];template<class T>inline void read(T &x){x = 0; bool fl = 0; char c = getchar();while (!isdigit(c)){if (c == '-') fl = 1; c = getchar();}while (isdigit(c)){x = (x<<3)+(x<<1)+c-'0'; c = getchar();}if (fl) x = -x;
}void dfs(int u, int fa)
{faz[u] = fa;dpt[u] = dpt[fa]+1;siz[u] = 1;son[u] = -1;for (int i = h[u]; i; i = nxt[i])if (v[i] != fa){dfs(v[i], u);siz[u] += siz[v[i]];if (son[u] == -1 || siz[v[i]] > siz[son[u]]) son[u] = v[i];}
}void dfs1(int u, int _tp)
{top[u] = _tp;dfn[++idx] = u;rfn[u] = idx;if (son[u] != -1) dfs1(son[u], _tp);for (int i = h[u]; i; i = nxt[i])if (v[i] != faz[u] && v[i] != son[u])dfs1(v[i], v[i]);
}void modify(int &u, int l, int r, int P, int X)
{if (!u) u = ++tcnt;if (l == r){t[u] = node(X); return;}int mid = l+r>>1;if (P <= mid) modify(ch[u][0], l, mid, P, X);else modify(ch[u][1], mid+1, r, P, X);t[u] = t[ch[u][0]]+t[ch[u][1]];
}node query(int u, int l, int r, int L, int R)
{if (!u) return node(0);if (L <= l && r <= R) return t[u];int mid = l+r>>1;if (mid < L) return query(ch[u][1], mid+1, r, L, R);else if (R <= mid) return query(ch[u][0], l, mid, L, R);else return query(ch[u][0], l, mid, L, R)+query(ch[u][1], mid+1, r, L, R);
}node ask(int x, int y, int c)
{node ans = node(0);while (top[x] != top[y]){if (dpt[top[x]] < dpt[top[y]]) swap(x, y);ans = ans+query(root[c], 1, n, rfn[top[x]], rfn[x]);x = faz[top[x]];}if (dpt[x] > dpt[y]) swap(x, y);ans = ans+query(root[c], 1, n, rfn[x], rfn[y]);return ans;
}int main()
{read(n); read(q); m = 1e5;for (int i = 1; i <= n; ++ i) read(w[i]), read(c[i]);clear();for (int i = 1; i < n; ++ i){int x, y;read(x); read(y);add_undir(x, y);}dfs(1, 0);dfs1(1, 1);memset(root, 0, sizeof root); tcnt = 0;for (int i = 1; i <= n; ++ i)modify(root[c[i]], 1, n, rfn[i], w[i]);for (int i = 1; i <= q; ++ i){char s[2]; int x, y;scanf("%s", s); read(x); read(y);if (s[1] == 'W'){modify(root[c[x]], 1, n, rfn[x], y);w[x] = y;}else if (s[1] == 'C'){modify(root[c[x]], 1, n, rfn[x], 0);modify(root[y], 1, n, rfn[x], w[x]);c[x] = y;}else if (s[1] == 'S') printf("%d\n", ask(x, y, c[x]).tsum);else if (s[1] == 'M') printf("%d\n", ask(x, y, c[x]).tmax);}return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！