We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
static inline Word lowestOneBit(Word v) {
return v & (~v+1);
}
static inline Word highestOneBitMask(Word v) {
v |= v >> 1;
v |= v >> 2;
v |= v >> 4;
v |= v >> 8;
v |= v >> 16;
return v >> 1;
}
std::vector<Word> indices; //Vertex -> index
std::vector<Word> maxHIndices; //Vertex -> index
std::vector<Word> ancestorHeights; //Vertex -> Word
std::vector<Vertex> pathParents; //index-1 -> Vertex
struct SegmentTree {
vector leafs;
vector nodes;
vector laziness;
vector leftpos, rightpos;
int n, n2;
void init(int n_, const Val &v = Val()) { init(vector(n_, v)); }
void init(const vector &u) {
n = 2; while(n < (int)u.size()) n *= 2;
n2 = (n - 1) / 2 + 1;
leafs = u; leafs.resize(n, Val());
nodes.resize(n);
for(int i = n-1; i >= n2; -- i)
nodes[i] = Sum(leafs[i*2-n], i*2-n) + Sum(leafs[i*2+1-n], i*2+1-n);
for(int i = n2-1; i > 0; -- i)
nodes[i] = nodes[i*2] + nodes[i*2+1];
laziness.assign(n, Laziness());
leftpos.resize(n); rightpos.resize(n);
for(int i = n-1; i >= n2; -- i) {
leftpos[i] = i*2-n;
rightpos[i] = (i*2+1-n) + 1;
}
for(int i = n2-1; i > 0; -- i) {
leftpos[i] = leftpos[i*2];
rightpos[i] = rightpos[i*2+1];
}
}
Val get(int i) {
static int indices[128];
int k = getIndices(indices, i, i+1);
propagateRange(indices, k);
return leafs[i];
}
Sum getRange(int i, int j) {
static int indices[128];
int k = getIndices(indices, i, j);
propagateRange(indices, k);
Sum res = Sum();
for(int l = i + n, r = j + n; l < r; l >>= 1, r >>= 1) {
if(l & 1) res += sum(l ++);
if(r & 1) res += sum(-- r);
}
return res;
}
void set(int i, const Val &x) {
static int indices[128];
int k = getIndices(indices, i, i+1);
propagateRange(indices, k);
leafs[i] = x;
mergeRange(indices, k);
}
void addToRange(int i, int j, const Laziness &x) {
if(i >= j) return;
static int indices[128];
int k = getIndices(indices, i, j);
propagateRange(indices, k);
int l = i + n, r = j + n;
if(l & 1) { int p = (l ++) - n; x.addToVal(leafs[p], p); }
if(r & 1) { int p = (-- r) - n; x.addToVal(leafs[p], p); }
for(l >>= 1, r >>= 1; l < r; l >>= 1, r >>= 1) {
if(l & 1) laziness[l ++] += x;
if(r & 1) laziness[-- r] += x;
}
mergeRange(indices, k);
}
private:
int getIndices(int indices[128], int i, int j) {
int k = 0, l, r;
if(i >= j) return 0;
for(l = (n + i) >> 1, r = (n + j - 1) >> 1; l != r; l >>= 1, r >>= 1) {
indices[k ++] = l;
indices[k ++] = r;
}
for(; l; l >>= 1) indices[k ++] = l;
return k;
}
void propagateRange(int indices[], int k) {
for(int i = k - 1; i >= 0; -- i)
propagate(indices[i]);
}
void mergeRange(int indices[], int k) {
for(int i = 0; i < k; ++ i)
merge(indices[i]);
}
inline void propagate(int i) {
if(i >= n) return;
laziness[i].addToSum(nodes[i], leftpos[i], rightpos[i]);
if(i * 2 < n) {
laziness[i * 2] += laziness[i];
laziness[i * 2 + 1] += laziness[i];
}else {
laziness[i].addToVal(leafs[i * 2 - n], i * 2);
laziness[i].addToVal(leafs[i * 2 + 1 - n], i * 2 + 1);
}
laziness[i] = Laziness();
}
inline void merge(int i) {
if(i >= n) return;
nodes[i] = sum(i * 2) + sum(i * 2 + 1);
}
inline Sum sum(int i) {
propagate(i);
return i < n ? nodes[i] : Sum(leafs[i - n], i - n);
}
};
vector t_parent;
vi t_seq; vector t_sign;
vector t_left, t_right;
void tree_signedeulertour(const vector &g, int root) {
int n = g.size();
t_parent.assign(n, -1);
t_left.assign(n, -1);
t_right.assign(n, -1);
t_seq.assign(n * 2, -1);
t_sign.assign(n * 2, false);
int pos = 0;
int main() {
int N, Q, root;
scanf("%d%d%d", &N, &Q, &root), root --;
vector g(N);
rep(i, N-1) {
int a, b;
scanf("%d%d", &a, &b), a --, b --;
g[a].pb(b);
g[b].pb(a);
}
tree_signedeulertour(g, root);
vi depth(N, -1);
rep(ix, t_seq.size()) if(!t_sign[ix]) {
int i = t_seq[ix];
depth[i] = i == root ? 0 : depth[t_parent[i]] + 1;
}
vector<SchieberVishkinLCA::Graph::Edge> edges;
rep(i, N) if(i != root) {
edges.push_back(SchieberVishkinLCA::Graph::Edge(t_parent[i], i));
}
SchieberVishkinLCA lca;
SchieberVishkinLCA::Graph gg; gg.init(N, edges);
lca.build(gg, root);
SegmentTree segt;
{ vector<Val> vals;
rep(i, t_seq.size())
vals.push_back(Val(t_sign[i], 0, depth[t_seq[i]]));
segt.init(vals);
}
rep(ii, Q) {
static char q[2];
scanf("%s", q);
if(*q == 'U') {
int T, V, K;
scanf("%d%d%d", &T, &V, &K), T --;
Laziness l(mint(V) - mint(K) * depth[T], K);
segt.addToRange(t_left[T], t_right[T], l);
}else {
int A, B;
scanf("%d%d", &A, &B), A --, B --;
int C = lca.query(A, B);
mint ans = 0;
ans += segt.getRange(t_left[C], t_left[A]+1).signedSum;
ans += segt.getRange(t_left[C]+1, t_left[B]+1).signedSum;
printf("%d\n", ans.get());
}
}
return 0;
}
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Rooted Tree
You are viewing a single comment's thread. Return to all comments →
using namespace std; typedef vector vi; typedef pair pii; typedef vector > vpii; typedef long long ll; typedef vector vl; typedef pair pll; typedef vector > vpll; typedef vector vs; typedef long double ld; template inline void amin(T &x, U y) { if(y < x) x = y; } template inline void amax(T &x, U y) { if(x < y) x = y; }
struct To { typedef int Vertex; Vertex to; To() { } To(Vertex to_): to(to_) { } };
template struct StaticGraph { typedef To_ To; typedef typename To::Vertex Vertex; typedef std::pair Edge; typedef const To *const_iterator;
private: int n; std::vector tos; std::vector offsets; };
class SchieberVishkinLCA { public: typedef StaticGraph Graph; typedef unsigned Word; typedef Graph::Vertex Vertex; private:
public: //g????????????? void build(const Graph &g, Vertex root) { return build(g, std::vector(1, root)); } void build(const Graph &g, const std::vector &roots) { int N = g.numVertices();
};
template struct ModInt { static const int Mod = MOD; unsigned x; ModInt(): x(0) { } ModInt(signed sig) { int sigt = sig % MOD; if(sigt < 0) sigt += MOD; x = sigt; } ModInt(signed long long sig) { int sigt = sig % MOD; if(sigt < 0) sigt += MOD; x = sigt; } int get() const { return (int)x; }
}; typedef ModInt<1000000007> mint;
struct Val { bool sign; mint x; int depth; Val() { } Val(bool sign_, mint x_, int depth_): sign(sign_), x(x_), depth(depth_) { } };
struct Sum { mint signedSum, signedDepthSum, signedCount; Sum(): signedSum(0), signedDepthSum(0), signedCount(0) { } Sum(const Val &val, int pos) { bool sign = val.sign; signedDepthSum = !sign ? val.depth : -val.depth; signedSum = !sign ? val.x : -val.x; signedCount = !sign ? 1 : -1; } Sum &operator+=(const Sum &that) { signedSum += that.signedSum; signedDepthSum += that.signedDepthSum; signedCount += that.signedCount; return *this; } Sum operator+(const Sum &that) const { return Sum(*this) += that; } };
struct Laziness { mint add0, add1; Laziness(): add0(0), add1(0) { } Laziness(mint add0_, mint add1_): add0(add0_), add1(add1_) { } Laziness &operator+=(const Laziness &that) { add0 += that.add0; add1 += that.add1; return *this; } void addToVal(Val &val, int pos_) const { val.x += add0 + add1 * val.depth; } void addToSum(Sum &sum, int left_, int right_) const { sum.signedSum += add0 * sum.signedCount + add1 * sum.signedDepthSum; } };
struct SegmentTree { vector leafs; vector nodes; vector laziness; vector leftpos, rightpos; int n, n2; void init(int n_, const Val &v = Val()) { init(vector(n_, v)); } void init(const vector &u) { n = 2; while(n < (int)u.size()) n *= 2; n2 = (n - 1) / 2 + 1; leafs = u; leafs.resize(n, Val()); nodes.resize(n); for(int i = n-1; i >= n2; -- i) nodes[i] = Sum(leafs[i*2-n], i*2-n) + Sum(leafs[i*2+1-n], i*2+1-n); for(int i = n2-1; i > 0; -- i) nodes[i] = nodes[i*2] + nodes[i*2+1]; laziness.assign(n, Laziness());
private: int getIndices(int indices[128], int i, int j) { int k = 0, l, r; if(i >= j) return 0; for(l = (n + i) >> 1, r = (n + j - 1) >> 1; l != r; l >>= 1, r >>= 1) { indices[k ++] = l; indices[k ++] = r; } for(; l; l >>= 1) indices[k ++] = l; return k; } void propagateRange(int indices[], int k) { for(int i = k - 1; i >= 0; -- i) propagate(indices[i]); } void mergeRange(int indices[], int k) { for(int i = 0; i < k; ++ i) merge(indices[i]); } inline void propagate(int i) { if(i >= n) return; laziness[i].addToSum(nodes[i], leftpos[i], rightpos[i]); if(i * 2 < n) { laziness[i * 2] += laziness[i]; laziness[i * 2 + 1] += laziness[i]; }else { laziness[i].addToVal(leafs[i * 2 - n], i * 2); laziness[i].addToVal(leafs[i * 2 + 1 - n], i * 2 + 1); } laziness[i] = Laziness(); } inline void merge(int i) { if(i >= n) return; nodes[i] = sum(i * 2) + sum(i * 2 + 1); } inline Sum sum(int i) { propagate(i); return i < n ? nodes[i] : Sum(leafs[i - n], i - n); } };
vector t_parent; vi t_seq; vector t_sign; vector t_left, t_right;
void tree_signedeulertour(const vector &g, int root) { int n = g.size(); t_parent.assign(n, -1); t_left.assign(n, -1); t_right.assign(n, -1); t_seq.assign(n * 2, -1); t_sign.assign(n * 2, false); int pos = 0;
}
int main() { int N, Q, root; scanf("%d%d%d", &N, &Q, &root), root --; vector g(N); rep(i, N-1) { int a, b; scanf("%d%d", &a, &b), a --, b --; g[a].pb(b); g[b].pb(a); } tree_signedeulertour(g, root); vi depth(N, -1); rep(ix, t_seq.size()) if(!t_sign[ix]) { int i = t_seq[ix]; depth[i] = i == root ? 0 : depth[t_parent[i]] + 1; }
}