Cerinta completa
You are given a tree with N nodes and each has a value associated with it. You are given Q queries, each of which is either an update or a retrieval operation.
Initially all node values are zero.
The update query is of the format
a1 d1 a2 d2 A B
This means you’d have to add in all nodes in the path from A to B where is the distance between the node and A.
The retrieval query is of the format
i j
You need to return the sum of the node values lying in the path from node i to node j modulo 1000000007.
Note:
- First all update queries are given and then all retrieval queries.
- Distance between 2 nodes is the shortest path length between them taking each edge weight as 1.
Input Format
The first line contains two integers (N and R respectively) separated by a space.
In the next N-1 lines, the ith line describes the ith edge: a line with two integers x y separated by a single space denotes an edge between nodes x and y.
The next line contains 2 space separated integers (U and Q respectively) representing the number of Update and Query operations to follow.
U lines follow. Each of the next U lines contains 6 space separated integers (a1,d1,a2,d2,A and B respectively).
Each of the next Q lines contains 2 space separated integers, i and j respectively.
Output Format
It contains exactly Q lines and each line containing the answer of the ith query.
Constraints
2 <= N <= 105
2 <= R <= 109
1 <= U <= 105
1 <= Q <= 105
1 <= a1,a2,d1,d2 <= 108
1 <= x, y, i, j, A, B <= N
Note
For the update operation, x can be equal to y and for the query operation, i can be equal to j.
Sample Input
7 2
1 2
1 3
2 4
2 6
4 5
6 7
1 4
1 1 1 1 4 6
4 5
2 7
4 7
5 3
Sample Output
1
44
45
9
Explanation
The node values after updation becomes :
0 8 0 1 0 36 0
Answer to Query #1: 1+0 = 1
Answer to Query #2: 8+36+0 = 44
Answer to Query #3: 1+8+36+0 = 45
Answer to Query #4: 0+1+8+0+0 = 9
Limbajul de programare folosit: cpp14
Cod:
#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>
#include <limits>
#include <functional>
#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;
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; }
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) { return *this *= that.inverse(); }
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/(ModInt that) const { return ModInt(*this) /= that; }
ModInt inverse() const {
long long a = x, b = MOD, u = 1, v = 0;
while(b) {
long long t = a / b;
a -= t * b; std::swap(a, b);
u -= t * v; std::swap(u, v);
}
return ModInt(u);
}
ModInt operator-() const { ModInt t; t.x = x == 0 ? 0 : Mod - x; return t; }
};
typedef ModInt<1000000007> mint;
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 treeLCA
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 treeI(x)), I(x) = maxHIndices[x])
//(hI(lca(v,u)) = j)hI(v)hI(u)
Vertex x, y;
if(j == hIv) x = v;
else { //lcav
Word kMask = highestOneBitMask(ancestorHeights[v] & (j-1)); //vj
x = pathParents[(indices[v] & ~kMask | (kMask+1))-1]; //indices[v]k
}
if(j == hIu) y = u;
else { //lcau
Word kMask = highestOneBitMask(ancestorHeights[u] & (j-1)); //uj
y = pathParents[(indices[u] & ~kMask | (kMask+1))-1]; //indices[u]k
}
return indices[x] < indices[y] ? x : y; //in-order
}
};
vector<int> t_parent;
vi t_ord;
void tree_getorder(const vector<vi> &g, int root) {
int n = g.size();
t_parent.assign(n, -1);
t_ord.clear();
vector<int> stk; stk.push_back(root);
while(!stk.empty()) {
int i = stk.back(); stk.pop_back();
t_ord.push_back(i);
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;
}
}
}
void querysub(vector<mint> &adds, int A, int B, mint x) {
adds[A] += x;
adds[B] -= x;
}
int main() {
typedef StaticGraph<To> Graph;
int N, R;
scanf("%d%d", &N, &R);
vector<vi> g(N);
rep(i, N-1) {
int x, y;
scanf("%d%d", &x, &y), -- x, -- y;
g[x].push_back(y);
g[y].push_back(x);
}
tree_getorder(g, 0);
vector<int> depth(N, 0);
reu(ix, 1, N) {
int i = t_ord[ix];
depth[i] = depth[t_parent[i]] + 1;
}
vector<Graph::Edge> edges;
reu(i, 1, N)
edges.push_back(Graph::Edge(t_parent[i], i));
Graph gg; gg.init(N, edges);
SchieberVishkinLCA lca; lca.build(gg, 0);
vector<mint> powRs(N*2+1);
powRs[N] = 1;
rer(i, 1, N) powRs[N+i] = powRs[N+i-1] * R;
mint invR = mint(R).inverse();
rer(i, 1, N) powRs[N-i] = powRs[N-i+1] * invR;
const int T = 6;
vector<mint> adds[T], coefs[T];
rep(t, T) coefs[t].assign(N+1, mint());
rep(i, N) {
int d = depth[i];
coefs[0][i] = powRs[N-d];
coefs[1][i] = powRs[N+d];
coefs[2][i] = powRs[N-d] * -d;
coefs[3][i] = powRs[N+d] * +d;
coefs[4][i] = powRs[N-d] * -d * -d;
coefs[5][i] = powRs[N+d] * +d * +d;
}
rep(t, T) adds[t].assign(N+1, mint());
vector<mint> values(N, mint());
int U, Q;
scanf("%d%d", &U, &Q);
rep(ii, U) {
int a1, d1, a2, d2, A, B;
scanf("%d%d%d%d%d%d", &a1, &d1, &a2, &d2, &A, &B), -- A, -- B;
//(a1 + z d1) (a2 + z d2) R^z
//= a1 a2 R^z + (a1 d2 + d1 a2) z R^z + d1 d2 z^2 R^z
int C = lca.query(A, B), Cp = C == 0 ? N : t_parent[C];
int dA = depth[A], dB = depth[B], dC = depth[C];
int uC = dA - dC, uB = dA + dB - dC * 2;
mint p = powRs[N+dA], q = powRs[N-dB+uB];
int e = -dB+uB;
//a1 a2 R^z
if(1) {
mint t = mint(a1) * a2;
querysub(adds[0], A, Cp, t * p);
querysub(adds[1], B, C, t * q);
}
//(a1 d2 + d1 a2) z R^z
if(1) {
mint t = mint(a1) * d2 + mint(d1) * a2;
querysub(adds[2], A, Cp, t * p);
querysub(adds[0], A, Cp, t * p * dA);
querysub(adds[3], B, C, t * q);
querysub(adds[1], B, C, t * q * e);
}
//d1 d2 z^2 R^z
if(1) {
mint t = mint(d1) * d2;
querysub(adds[4], A, Cp, t * p);
querysub(adds[2], A, Cp, t * p * dA * 2);
querysub(adds[0], A, Cp, t * p * dA * dA);
querysub(adds[5], B, C, t * q);
querysub(adds[3], B, C, t * q * e * 2);
querysub(adds[1], B, C, t * q * e * e);
}
}
rep(t, T) {
for(int ix = N-1; ix > 0; -- ix) {
int i = t_ord[ix];
adds[t][t_parent[i]] += adds[t][i];
}
rep(i, N)
adds[t][i] *= coefs[t][i];
// cerr << t << ": "; rep(i, N) cerr << adds[t][i].get() << ", "; cerr << endl;
rep(i, N)
values[i] += adds[t][i];
adds[t].assign(N+1, mint());
}
// cerr << "values: "; rep(i, N) cerr << values[i].get() << ", "; cerr << endl;
// }
vector<mint> sums = values;
for(int ix = 1; ix < N; ++ ix) {
int i = t_ord[ix];
sums[i] += sums[t_parent[i]];
}
rep(ii, Q) {
int A, B;
scanf("%d%d", &A, &B), -- A, -- B;
int C = lca.query(A, B);
mint ans = 0;
ans += sums[A];
ans += sums[B];
ans -= values[C];
if(C != 0)
ans -= sums[t_parent[C]] * 2;
printf("%d\n", ans.get());
}
return 0;
}
Scor obtinut: 1.0
Submission ID: 464654047
Link challenge: https://www.hackerrank.com/challenges/easy-addition/problem
Easy Addition