【链接】
【题意】
给你一棵树,每个节点上都有一个权值.
然后给你m个询问,每个询问(x,y,a,b);
表示询问x->y这条路径上权值在[a,b]范围内的节点的权值和.
【题解】
树链剖分题。
在树链上建一个线段树,线段树的每个节点存3个值,max[i],min[i],sum[i]分别表示这个区间里面的数的最大值、最小值、以及权值和。
然后在线段树上做查找(a,b)范围内的数的权值和。
如果该节点在路径上,那么如果a<=min[i] && max[i] <= b的话,直接返回sum[i],否则如果不在范围里,直接范围0(肯定不在的话);
如果没办法确定在不在,则继续往下走。
【错的次数】
2
【反思】
关了同步之后,不能用puts("");
【代码】
#include#include #include using namespace std;const int N = 1e5;int n, m, c[N + 10], uppest[N + 10], idx[N + 10], cnt, sz[N + 10], dep[N + 10];long long sum[(N + 10) << 2];int mi[(N + 10) << 2], ma[(N + 10) << 2], a, b, fat[N + 10];vector g[N + 10];void dfs1(int x, int fa) { sz[x] = 1; for (int y : g[x]) { if (y == fa) continue; dep[y] = dep[x] + 1; dfs1(y, x); sz[x] += sz[y]; fat[y] = x; }}void dfs2(int x, int chain) { idx[x] = ++cnt; uppest[x] = chain; int ma = 0; for (int y : g[x]) { if (dep[y] > dep[x] && sz[y] > sz[ma]) { ma = y; } } if (ma == 0) return; dfs2(ma, chain); for (int y : g[x]) if (dep[y] > dep[x] && y != ma) dfs2(y, y);}void updata(int pos, int x, int l, int r, int rt) { if (l == r) { mi[rt] = ma[rt] = x; sum[rt] = x; return; } int m = (l + r) >> 1; if (pos <= m) updata(pos, x, l, m, rt << 1); else updata(pos, x, m + 1, r, rt << 1 | 1); ma[rt] = max(ma[rt << 1 | 1], ma[rt << 1]); mi[rt] = min(mi[rt << 1 | 1], mi[rt << 1]); sum[rt] = sum[rt << 1] + sum[rt << 1 | 1];}void pre() { for (int i = 1; i <= n; i++) updata(idx[i], c[i], 1, n, 1);}long long get_ans(int L, int R, int l, int r, int rt) { if (L <= l && r <= R) { if (ma[rt] < a) return 0; if (mi[rt] > b) return 0; if (a <= mi[rt] && ma[rt] <= b) return sum[rt]; } int m = (l + r) >> 1; long long temp = 0; if (L <= m) temp += get_ans(L, R, l, m, rt << 1); if (m < R) temp += get_ans(L, R, m + 1, r, rt << 1 | 1); return temp;}long long calc(int x, int y) { long long temp = 0; while (uppest[x] != uppest[y]) { if (dep[uppest[x]] > dep[uppest[y]]) swap(x, y); //dep[x] < dep[y] ok temp += get_ans(idx[uppest[y]], idx[y], 1, n, 1); y = fat[uppest[y]]; } if (dep[x] > dep[y]) swap(x, y); temp += get_ans(idx[x], idx[y], 1, n, 1); return temp;}void deal() { for (int i = 1; i <= m; i++) { int s, t; cin >> s >> t >> a >> b; cout << calc(s, t); if (i == m) cout << endl; else cout << ' '; }}int main() { //freopen("F:\\rush.txt", "r", stdin); ios::sync_with_stdio(0), cin.tie(0); while (cin >> n >> m) { for (int i = 1; i <= n; i++) cin >> c[i]; for (int i = 1; i <= n; i++) g[i].clear(); for (int i = 1; i <= n - 1; i++) { int x, y; cin >> x >> y; g[x].push_back(y), g[y].push_back(x); } dep[1] = 0; dfs1(1, 0); cnt = 0; dfs2(1, 1); pre(); deal(); } return 0;}