「2017 山东一轮集训 Day5」距离

it2022-05-06  6

/* 写完开店再写这个题目顿时神清气爽, 腰也不疼了, 眼也不花了 首先考虑将询问拆开, 就是查询一些到根的链和点k的关系 根据我们开店的结论, 一个点集到一个定点的距离和可以分三部分算 那么就很简单了吧QAQ, 在树上可持久化弄一下 */ #include<cstdio> #include<algorithm> #include<cstring> #include<queue> #include<iostream> #define ll long long #define mmp make_pair #define M 200010 using namespace std; int read() { int nm = 0, f = 1; char c = getchar(); for(; !isdigit(c); c = getchar()) if(c == '-') f = -1; for(; isdigit(c); c = getchar()) nm = nm * 10 + c - '0'; return nm * f; } int type, n, q, sz[M], son[M], fa[M], top[M], dfn[M], ver[M], dft, cnt, p[M], deep[M]; ll dis[M], sum[M], w[M], ans; vector<pair<int,int> > to[M]; int lc[20000100], rc[20000100], v[20000100], rt[M]; ll t[20000100]; void dfs(int now, int f) { deep[now] = deep[f] + 1; sz[now] = 1; fa[now] = f; for(int i = 0; i < to[now].size(); i++) { int vj = to[now][i].first, v = to[now][i].second; if(vj == f) continue; dis[vj] = dis[now] + v; ver[vj] = v; // deep[vj] = deep[now] + 1; dfs(vj, now); if(sz[vj] > sz[son[now]]) son[now] = vj; sz[now] += sz[vj]; } } void dfs(int now) { dfn[now] = ++cnt; w[cnt] = ver[now]; if(son[now]) { top[son[now]] = top[now]; dfs(son[now]); } for(int i = 0; i < to[now].size(); i++) { int vj = to[now][i].first; if(vj == fa[now] || vj == son[now]) continue; top[vj] = vj; dfs(vj); } } void modify(int last, int &now, int l, int r, int ln, int rn) { now = ++cnt; lc[now] = lc[last], rc[now] = rc[last], t[now] = t[last], v[now] = v[last]; if(l == ln && r == rn) { v[now]++; return; } t[now] += w[rn] - w[ln - 1]; int mid = (l + r) >> 1; if(ln > mid) modify(rc[last], rc[now], mid + 1, r, ln, rn); else if(rn <= mid) modify(lc[last], lc[now], l, mid, ln, rn); else modify(lc[last], lc[now], l, mid, ln, mid), modify(rc[last], rc[now], mid + 1, r, mid + 1, rn); } ll query(int now, int l, int r, int ln, int rn) { ll ans = 1ll * (w[rn] - w[ln - 1]) * v[now]; if(l == ln && r <= rn) return ans + t[now]; int mid = (l + r) >> 1; if(rn <= mid) return ans + query(lc[now], l, mid, ln, rn); else if(ln > mid) return ans + query(rc[now], mid + 1, r, ln, rn); else return ans + query(lc[now], l, mid, ln, mid) + query(rc[now], mid + 1, r, mid + 1, rn); } void Modify(int &now, int x) { for(; top[x] != 1; x = fa[top[x]]) modify(now, now, 1, n, dfn[top[x]], dfn[x]); modify(now, now, 1, n, dfn[1], dfn[x]); } void work(int now) { rt[now] = rt[fa[now]]; Modify(rt[now], p[now]); sum[now] = dis[p[now]] + sum[fa[now]]; for(int i = 0; i < to[now].size(); i ++) { int vj = to[now][i].first; if(vj == fa[now]) continue; work(vj); } } ll Query(int x, int k) { if(k == 0) return 0; // cout << k << " "; ll ans = sum[x]; ans += dis[k] * deep[x]; for(; top[k] != 1; k = fa[top[k]]) ans -= 2ll * query(rt[x], 1, n, dfn[top[k]], dfn[k]); ans -= 2ll *query(rt[x], 1, n, dfn[1], dfn[k]); // cout << x << " " << ans << "!!!!!!!\n"; return ans; } int LCA(int a, int b) { while(top[a] != top[b]) { if(deep[top[a]] < deep[top[b]]) swap(a, b); a = fa[top[a]]; } if(deep[a] > deep[b]) swap(a, b); return a; } int main() { type = read(); n = read(), q = read(); for(int i = 1; i < n; i++) { int vi = read(), vj = read(), v = read(); to[vi].push_back(mmp(vj, v)); to[vj].push_back(mmp(vi, v)); } for(int i = 1; i <= n; i++) p[i] = read(); dfs(1, 0); top[1] = 1; dfs(1); for(int i = 1; i <= n; i++) w[i] += w[i - 1]; work(1); while(q--) { ll vi = read() ^ ans, vj = read() ^ ans, k = read() ^ ans; int l = LCA(vi, vj); ans = Query(vi, k) + Query(vj, k) - Query(l, k) - Query(fa[l], k); cout << ans << "\n"; ans *= type; } return 0; }

转载于:https://www.cnblogs.com/luoyibujue/p/10620465.html


最新回复(0)