Cerinta completa
You are given a rooted tree with N nodes and the root of the tree, R, is also given. Each node of the tree contains a value, that is initially empty. You have to mantain the tree under two operations:
- Update Operation
- Report Operation
Update Operation
Each Update Operation begins with the character U. Character U is followed by 3 integers T, V and K. For every node which is the descendent of the node T, update it’s value by adding V + d*K, where V and K are the parameters of the query and d is the distance of the node from T. Note that V is added to node T.
Report Operation
Each Report Operation begins with the character Q. Character Q is followed by 2 integers, A and B. Output the sum of values of nodes in the path from A to B modulo (109 + 7)
Input Format
The first Line consists of 3 space separated integers, N E R, where N is the number of nodes present, E is the total number of queries (update + report), and R is root of the tree.
Each of the next N-1 lines contains 2 space separated integers, X and Y (X and Y are connected by an edge).
Thereafter, E lines follows: each line can represent either the Update Operation or the Report Operation.
- Update Operation is of the form : U T V K.
- Report Operation is of the form : Q A B.
Output Format
Output the answer for every given report operation.
Constraints
1 ≤ N, E ≤ 105
1 ≤ E ≤ 105
1 ≤ R, X, Y, T, A, B ≤ N
1 ≤ V, K ≤ 109
X ≠ Y
Sample Input
7 7 1
1 2
2 3
2 4
2 5
5 6
6 7
U 5 10 2
U 4 5 3
Q 1 7
U 6 7 4
Q 2 7
Q 1 4
Q 2 4
Sample Output
36
54
5
5
Explanation
- Values of Nodes after
U 5 10 2:[0 0 0 0 10 12 14]. - Values of Nodes after
U 4 5 3:[0 0 0 5 10 12 14]. - Sum of the Nodes from 1 to 7: 0 + 0 + 10 + 12 + 14 = 36.
- Values of Nodes after
U 6 7 4: [0 0 0 5 10 19 25]. - Sum of the Nodes from 2 to 7: 0 + 10 + 19 + 25 = 54.
- Sum of the Nodes from 1 to 4: 0 + 0 + 5 = 5.
- Sum of the Nodes from 2 to 4: 0 + 5 = 5.
Limbajul de programare folosit: cpp14
Cod:
#define _CRT_SECURE_NO_WARNINGS
#include <string>
#include <vector>
#include <algorithm>
#include <numeric>
#include <set>
#include <map>
#include <queue>
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cstring>
#include <cctype>
#include <cassert>
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
#if defined(_MSC_VER) || __cplusplus > 199711L
#define aut(r,v) auto r = (v)
#else
#define aut(r,v) typeof(v) r = (v)
#endif
#define each(it,o) for(aut(it, (o).begin()); it != (o).end(); ++ it)
#define all(o) (o).begin(), (o).end()
#define pb(x) push_back(x)
#define mp(x,y) make_pair((x),(y))
#define mset(m,v) memset(m,v,sizeof(m))
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3fLL
using namespace std;
typedef vector<int> vi; typedef pair<int,int> pii; typedef vector<pair<int,int> > vpii;
typedef long long ll; typedef vector<long long> vl; typedef pair<long long,long long> pll; typedef vector<pair<long long,long long> > vpll;
typedef vector<string> vs; typedef long double ld;
template<typename T, typename U> inline void amin(T &x, U y) { if(y < x) x = y; }
template<typename T, typename U> 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<typename To_>
struct StaticGraph {
typedef To_ To;
typedef typename To::Vertex Vertex;
typedef std::pair<Vertex,To> Edge;
typedef const To *const_iterator;
void init(int n_, const std::vector<Edge> &edges) {
n = n_; int m = edges.size();
tos.resize(m+1); offsets.resize(n+1);
for(int e = 0; e < m; e ++) offsets[edges[e].first] ++;
for(int v = 1; v <= n_; v ++) offsets[v] += offsets[v-1];
for(int e = 0; e < m; e ++)
tos[-- offsets[edges[e].first]] = edges[e].second;
}
int numVertices() const { return n; }
int numEdges() const { return tos.size() - 1; }
inline const_iterator edgesBegin(int v) const { return &tos[offsets[v]]; }
inline const_iterator edgesEnd(int v) const { return &tos[offsets[v+1]]; }
private:
int n;
std::vector<To> tos;
std::vector<int> offsets;
};
class SchieberVishkinLCA {
public:
typedef StaticGraph<To> Graph;
typedef unsigned Word;
typedef Graph::Vertex Vertex;
private:
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
public:
//g?????????????
void build(const Graph &g, Vertex root) {
return build(g, std::vector<Vertex>(1, root));
}
void build(const Graph &g, const std::vector<Vertex> &roots) {
int N = g.numVertices();
ancestorHeights.resize(N);
std::vector<Vertex> parents(N);
maxHIndices.resize(N);
std::vector<Vertex> vertices; vertices.reserve(N);
indices.resize(N);
//inorder traversal
Word currentIndex = 1;
for(int ri = 0; ri < (int)roots.size(); ri ++) {
Vertex root = roots[ri];
parents[root] = root; //???????
vertices.push_back(root);
}
while(!vertices.empty()) {
Vertex v = vertices.back(); vertices.pop_back();
indices[v] = currentIndex ++;
for(const Graph::To *it = g.edgesBegin(v); it != g.edgesEnd(v); ++ it) {
parents[it->to] = v;
vertices.push_back(it->to);
}
}
//BFS (???????????????)
int head = 0, tail = roots.size();
vertices.resize(N);
for(int ri = 0; ri < (int)roots.size(); ri ++)
vertices[ri] = roots[ri];
while(head != tail) {
Vertex v = vertices[head ++];
for(const Graph::To *it = g.edgesBegin(v); it != g.edgesEnd(v); ++ it)
vertices[tail ++] = it->to;
}
//?????
for(std::vector<Vertex>::const_iterator it = vertices.begin(); it != vertices.end(); ++ it)
maxHIndices[*it] = indices[*it];
for(std::vector<Vertex>::const_reverse_iterator it = vertices.rbegin(); it != vertices.rend(); ++ it) {
Vertex v = *it, parent = parents[v];
if(lowestOneBit(maxHIndices[parent]) < lowestOneBit(maxHIndices[v]))
maxHIndices[parent] = maxHIndices[v];
}
//A????
for(int ri = 0; ri < (int)roots.size(); ri ++) {
Vertex root = roots[ri];
ancestorHeights[root] = 0;
}
for(std::vector<Vertex>::const_iterator it = vertices.begin(); it != vertices.end(); ++ it) {
Vertex v = *it;
ancestorHeights[v] = ancestorHeights[parents[v]] | lowestOneBit(maxHIndices[v]);
}
pathParents.swap(parents); //???????
for(int ri = 0; ri < (int)roots.size(); ri ++) {
Vertex root = roots[ri];
pathParents[indices[root]-1] = root;
}
for(std::vector<Vertex>::const_iterator it = vertices.begin(); it != vertices.end(); ++ it) {
Vertex v = *it;
for(const Graph::To *jt = g.edgesBegin(v); jt != g.edgesEnd(v); ++ jt) {
if(maxHIndices[v] != maxHIndices[jt->to])
pathParents[indices[jt->to]-1] = v;
else
pathParents[indices[jt->to]-1] = pathParents[indices[v]-1];
}
}
}
Vertex query(Vertex v, Vertex u) const {
//binary tree???LCA???????
Word Iv = maxHIndices[v], Iu = maxHIndices[u];
Word hIv = lowestOneBit(Iv), hIu = lowestOneBit(Iu);
Word hbMask = highestOneBitMask((Iv ^ Iu) | hIv | hIu);
Word j = lowestOneBit(ancestorHeights[v] & ancestorHeights[u] & ~hbMask);
//j = hI(lca(v,u)) ??? (????hI(x) = 2^(complete binary tree???I(x)???), I(x) = maxHIndices[x])
//(hI(lca(v,u)) = j)?hI(v)?hI(u)????????????????????????…
Vertex x, y;
if(j == hIv) x = v;
else { //lca?v????????
Word kMask = highestOneBitMask(ancestorHeights[v] & (j-1)); //v?????j???????????????????
x = pathParents[(indices[v] & ~kMask | (kMask+1))-1]; //indices[v]?k???????????
}
if(j == hIu) y = u;
else { //lca?u????????
Word kMask = highestOneBitMask(ancestorHeights[u] & (j-1)); //u?????j???????????????????
y = pathParents[(indices[u] & ~kMask | (kMask+1))-1]; //indices[u]?k???????????
}
return indices[x] < indices[y] ? x : y; //in-order????????????????????
}
};
template<int MOD>
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; }
ModInt &operator+=(ModInt that) { if((x += that.x) >= MOD) x -= MOD; return *this; }
ModInt &operator-=(ModInt that) { if((x += MOD - that.x) >= MOD) x -= MOD; return *this; }
ModInt &operator*=(ModInt that) { x = (unsigned long long)x * that.x % MOD; return *this; }
ModInt operator+(ModInt that) const { return ModInt(*this) += that; }
ModInt operator-(ModInt that) const { return ModInt(*this) -= that; }
ModInt operator*(ModInt that) const { return ModInt(*this) *= that; }
ModInt operator-() const { ModInt t; t.x = x == 0 ? 0 : Mod - x; return t; }
};
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<Val> leafs;
vector<Sum> nodes;
vector<Laziness> laziness;
vector<int> leftpos, rightpos;
int n, n2;
void init(int n_, const Val &v = Val()) { init(vector<Val>(n_, v)); }
void init(const vector<Val> &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<int> t_parent;
vi t_seq; vector<bool> t_sign;
vector<int> t_left, t_right;
void tree_signedeulertour(const vector<vi> &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;
vector<int> stk; stk.push_back(root);
while(!stk.empty()) {
int i = stk.back(); stk.pop_back();
if(i < 0) {
i = -i - 1;
t_seq[pos] = i;
t_sign[pos] = true;
pos ++;
t_right[i] = pos;
continue;
}
t_left[i] = pos;
t_seq[pos] = i;
t_sign[pos] = false;
pos ++;
stk.push_back(-(i+1));
for(int j = (int)g[i].size()-1; j >= 0; j --) {
int c = g[i][j];
if(t_parent[c] == -1 && c != root)
stk.push_back(c);
else
t_parent[i] = c;
}
}
}
int main() {
int N, Q, root;
scanf("%d%d%d", &N, &Q, &root), root --;
vector<vi> 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;
}
Scor obtinut: 1.0
Submission ID: 464653998
Link challenge: https://www.hackerrank.com/challenges/rooted-tree/problem
Rooted Tree