Cerinta completa
Chinese Version
Russian Version
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.
The update query is of the format
i j X
This means you’d have to add a GP series to the nodes which lie in the path from node i to node j (both inclusive) with first term of the GP as X on node i and the common ratio as R (given in the input)
The retrieval query is of the format
i j
You need to return the sum of the node values (S) lying in the path from node i to node j modulo 100711433.
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 a b separated by a single space denotes an edge between a, b.
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 3 space separated integers (i,j, and X 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 <= 100000
2 <= R <= 109
1 <= U <= 100000
1 <= Q <= 100000
1 <= X <= 10
1 <= a, b, i, j <= N
Sample Input
6 2
1 2
1 4
2 6
4 5
4 3
2 2
1 6 3
5 3 5
6 4
5 1
Sample Output
31
18
Explanation
The node values after the first updation becomes :
3 6 0 0 0 12
The node values after second updation becomes :
3 6 20 10 5 12
Answer to Query #1: 12 + 6 + 3 + 10 = 31
Answer to Query #2: 5 + 10 +3 = 18
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 <list>
#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
#define EPS 1e-9
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(x > y) x = y; }
template<typename T, typename U> inline void amax(T &x, U y) { if(x < y) x = y; }
struct CentroidPathDecomposition {
vector<int> colors, positions; //Vertex -> Color, Vertex -> Offset
vector<int> lengths, parents, branches; //Color -> Int, Color -> Color, Color -> Offset
vector<int> parentnodes, depths; //Vertex -> Vertex, Vertex -> Int
//vector<...>????1???????????????sortNodes()??????
vector<int> sortednodes, offsets; //Index -> Vertex, Color -> Index
//???????????????????????????(???)
void build(const vector<vi> &g, int root) {
int n = g.size();
colors.assign(n, -1); positions.assign(n, -1);
lengths.clear(); parents.clear(); branches.clear();
parentnodes.assign(n, -1); depths.assign(n, -1);
vector<int> subtreesizes;
measure(g, root, subtreesizes);
struct State {
int i, len, parent;
State() { }
State(int i_, int l, int p): i(i_), len(l), parent(p) { }
};
depths[root] = 0;
vector<State> s;
s.push_back(State(root, 0, -1));
while(!s.empty()) {
State t = s.back(); s.pop_back();
int i = t.i, len = t.len;
int color = lengths.size();
if(t.parent != -2) {
assert(parents.size() == color);
parents.push_back(t.parent);
branches.push_back(len);
len = 0;
}
colors[i] = color;
positions[i] = len;
int maxsize = -1, maxj = -1;
each(j, g[i]) if(colors[*j] == -1) {
if(maxsize < subtreesizes[*j]) {
maxsize = subtreesizes[*j];
maxj = *j;
}
parentnodes[*j] = i;
depths[*j] = depths[i] + 1;
}
if(maxj == -1) {
lengths.push_back(len + 1);
}else {
each(j, g[i]) if(colors[*j] == -1 && *j != maxj)
s.push_back(State(*j, len, color));
s.push_back(State(maxj, len + 1, -2));
}
}
sortNodes();
}
void sortNodes() {
int n = colors.size(), m = lengths.size();
sortednodes.resize(n, -1);
offsets.resize(m + 1);
rep(i, m) offsets[i+1] = offsets[i] + lengths[i];
rep(i, n) sortednodes[offsets[colors[i]] + positions[i]] = i;
}
void get(int v, int &c, int &p) const {
c = colors[v]; p = positions[v];
}
bool go_up(int &c, int &p) const {
p = branches[c]; c = parents[c];
return c != -1;
}
inline const int *nodesBegin(int c) const { return &sortednodes[0] + offsets[c]; }
inline const int *nodesEnd(int c) const { return &sortednodes[0] + offsets[c+1]; }
private:
void measure(const vector<vi> &g, int root, vector<int> &out_subtreesizes) const {
out_subtreesizes.assign(g.size(), -1);
vector<int> s;
s.push_back(root);
while(!s.empty()) {
int i = s.back(); s.pop_back();
if(out_subtreesizes[i] == -2) {
int s = 1;
each(j, g[i]) if(out_subtreesizes[*j] != -2)
s += out_subtreesizes[*j];
out_subtreesizes[i] = s;
}else {
s.push_back(i);
each(j, g[i]) if(out_subtreesizes[*j] == -1)
s.push_back(*j);
out_subtreesizes[i] = -2;
}
}
}
};
typedef int Vertex;
struct Graph {
typedef std::pair<Vertex, Vertex> Edge;
struct To {
Vertex to;
};
int n, m;
Graph(int n_, const std::vector<Edge> &edges):
n(n_), m(edges.size()), tos(m+1), offsets(n+1, 0) {
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]].to = edges[e].second;
}
inline const To *edgesBegin(int v) const { return &tos[offsets[v]]; }
inline const To *edgesEnd(int v) const { return &tos[offsets[v+1]]; }
inline const int outDegree(int v) const { return offsets[v+1] - offsets[v]; }
private:
std::vector<To> tos;
std::vector<int> offsets;
};
class SchieberVishkinLCA {
public:
typedef unsigned Word;
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) {
assert(g.m == g.n - 1);
ancestorHeights.resize(g.n);
std::vector<Vertex> parents(g.n);
maxHIndices.resize(g.n);
std::vector<Vertex> vertices; vertices.reserve(g.n);
indices.resize(g.n);
//euler tour
Word currentIndex = 1;
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 = 1;
vertices.resize(g.n); vertices[0] = root;
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????
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); //???????
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????????????????????
}
};
void direct_tree(const vector<vi> &g, int i, int parent, vector<pii> &out_edges) {
each(j, g[i]) if(*j != parent) {
out_edges.pb(mp(i, *j));
direct_tree(g, *j, i, out_edges);
}
}
template<int MOD>
struct ModInt {
static const int Mod = MOD;
int x;
ModInt(): x(0) { }
ModInt(signed sig) { if((x = sig % MOD + MOD) >= MOD) x -= MOD; }
ModInt(signed long long sig) { if((x = sig % MOD + MOD) >= MOD) x -= MOD; }
int get() const { return 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);
}
bool operator==(ModInt that) const { return x == that.x; }
bool operator!=(ModInt that) const { return x != that.x; }
ModInt operator-() const { ModInt t; t.x = x == 0 ? 0 : Mod - x; return t; }
};
typedef ModInt<100711433> mint;
mint powR[100001], powinvR[100001];
mint up[100001], down[100001];
mint sum[100001];
int main() {
int N, R, invR, U, Q;
scanf("%d%d", &N, &R);
invR = mint(R).inverse().get();
powR[0] = powinvR[0] = 1;
reu(i, 1, N+1) powR[i] = powR[i-1] * R;
reu(i, 1, N+1) powinvR[i] = powinvR[i-1] * invR;
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);
}
vector<pii> edges;
direct_tree(g, 0, -1, edges);
CentroidPathDecomposition cpd; cpd.build(g, 0);
SchieberVishkinLCA lca; lca.build(Graph(N, edges), 0);
mset(up, 0); mset(down, 0);
scanf("%d%d", &U, &Q);
rep(ii, U) {
int a, b, X;
scanf("%d%d%d", &a, &b, &X); a --, b --;
int l = lca.query(a, b);
int c, p, lc, lp;
cpd.get(l, lc, lp);
mint x = X;
cpd.get(a, c, p);
while(1) {
int k = cpd.offsets[c], kp = k + p, k0 = k + (c == lc ? lp : 0);
up[k + p] += x;
x *= powR[kp - k0 + 1];
if(k0) up[k0 - 1] -= x;
if(c == lc) break;
cpd.go_up(c, p);
}
int len = cpd.depths[a] + cpd.depths[b] - cpd.depths[l] * 2;
x = powR[len] * X;
cpd.get(b, c, p);
while(1) {
int k = cpd.offsets[c], kp = k + p, k0 = k + (c == lc ? lp + 1 : 0);
int h = kp - k0 + 1;
mint nx = x * powinvR[h];
down[k0] += nx * R;
down[kp + 1] -= x * R;
if(c == lc) break;
x = nx;
cpd.go_up(c, p);
}
}
for(int i = N-1; i > 0; i --) up[i-1] += up[i] * R;
for(int i = 0; i < N; i ++) down[i+1] += down[i] * R;
sum[0] = 0;
rep(i, N) sum[i+1] = sum[i] + up[i] + down[i];
rep(ii, Q) {
int a, b;
scanf("%d%d", &a, &b); a --, b --;
int l = lca.query(a, b);
int c, p, lc, lp;
cpd.get(l, lc, lp);
cpd.get(a, c, p);
mint ans = 0;
while(1) {
int k = cpd.offsets[c], kp = k + p, k0 = k + (c == lc ? lp : 0);
ans += sum[kp+1] - sum[k0];
if(c == lc) break;
cpd.go_up(c, p);
}
cpd.get(b, c, p);
while(1) {
int k = cpd.offsets[c], kp = k + p, k0 = k + (c == lc ? lp + 1 : 0);
ans += sum[kp+1] - sum[k0];
if(c == lc) break;
cpd.go_up(c, p);
}
printf("%d\n", ans.get());
}
return 0;
}
Scor obtinut: 1.0
Submission ID: 464653726
Link challenge: https://www.hackerrank.com/challenges/recalling-early-days-gp-with-trees/problem
Recalling Early Days GP with Trees