Soluție HackerRank pentru White Falcon And Tree. Include cerința formatată, exemple, explicația pașilor și cod sursă.
- Problemă: White Falcon And Tree
Cerinta completa
White Falcon has a tree with [Expresie matematică indisponibilă în copia arhivată] nodes. Each node contains a linear function. Let’s denote by [Expresie matematică indisponibilă în copia arhivată] the linear function contained in the node [Expresie matematică indisponibilă în copia arhivată].
Let’s denote the path from node [Expresie matematică indisponibilă în copia arhivată] to node [Expresie matematică indisponibilă în copia arhivată] like this: [Expresie matematică indisponibilă în copia arhivată], where [Expresie matematică indisponibilă în copia arhivată] and [Expresie matematică indisponibilă în copia arhivată], and [Expresie matematică indisponibilă în copia arhivată] and [Expresie matematică indisponibilă în copia arhivată] are connected.
White Falcon also has [Expresie matematică indisponibilă în copia arhivată] queries. They are in the following format:
-
[Expresie matematică indisponibilă în copia arhivată] [Expresie matematică indisponibilă în copia arhivată] [Expresie matematică indisponibilă în copia arhivată] [Expresie matematică indisponibilă în copia arhivată] [Expresie matematică indisponibilă în copia arhivată]. Assign [Expresie matematică indisponibilă în copia arhivată] as the function of all the nodes on the path from [Expresie matematică indisponibilă în copia arhivată] to [Expresie matematică indisponibilă în copia arhivată], i.e., [Expresie matematică indisponibilă în copia arhivată] is changed to [Expresie matematică indisponibilă în copia arhivată] where [Expresie matematică indisponibilă în copia arhivată] is the path from [Expresie matematică indisponibilă în copia arhivată] to [Expresie matematică indisponibilă în copia arhivată].
-
[Expresie matematică indisponibilă în copia arhivată] [Expresie matematică indisponibilă în copia arhivată] [Expresie matematică indisponibilă în copia arhivată] [Expresie matematică indisponibilă în copia arhivată]. Calculate [Expresie matematică indisponibilă în copia arhivată] modulo [Expresie matematică indisponibilă în copia arhivată]
Input Format
The first line contains [Expresie matematică indisponibilă în copia arhivată], the number of nodes. The following [Expresie matematică indisponibilă în copia arhivată] lines each contain two integers [Expresie matematică indisponibilă în copia arhivată] and [Expresie matematică indisponibilă în copia arhivată] that describe the function [Expresie matematică indisponibilă în copia arhivată].
Following [Expresie matematică indisponibilă în copia arhivată] lines contain edges of the tree.
The next line contains [Expresie matematică indisponibilă în copia arhivată], the number of queries. Each subsequent line contains one of the queries described above.
Output Format
For every query of the second kind, print one line containing an integer, the answer for that query.
Constraints
[Expresie matematică indisponibilă în copia arhivată] (Number of nodes)
[Expresie matematică indisponibilă în copia arhivată] (Number of queries)
[Expresie matematică indisponibilă în copia arhivată]
Sample Input
2
1 1
1 2
1 2
2
1 2 2 1 1
2 1 2 1
Sample Output
3
Explanation
[Expresie matematică indisponibilă în copia arhivată]
[Expresie matematică indisponibilă în copia arhivată]
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>
#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; 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; }
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; }
};
typedef ModInt<1000000007> mint;
//y = ax + b
struct LinearExpr {
mint a, b;
LinearExpr(): a(1), b(0) { }
LinearExpr(mint a_, mint b_): a(a_), b(b_) { }
LinearExpr(const LinearExpr &val, int) { a = val.a, b = val.b; }
LinearExpr &operator+=(const LinearExpr &that) {
b = b * that.a + that.b;
a = a * that.a;
return *this;
}
LinearExpr operator+(const LinearExpr &that) const {
return LinearExpr(*this) += that;
}
LinearExpr operator*(int k) const {
LinearExpr a = *this, r;
while(k) {
if(k & 1) r += a;
a += a;
k >>= 1;
}
return r;
}
mint evalute(mint x) const { return a * x + b; }
};
typedef LinearExpr Val;
struct Sum {
LinearExpr forward, backward;
Sum(): forward(), backward() { }
Sum(const Val &val, int): forward(val), backward(val) { }
Sum &operator+=(const Sum &that) {
forward += that.forward;
backward = that.backward + backward;
return *this;
}
Sum operator+(const Sum &that) const { return Sum(*this) += that; }
};
struct Laziness {
bool fill;
LinearExpr expr;
Laziness(): fill(false) { }
Laziness(LinearExpr expr_): fill(true), expr(expr_) { }
Laziness &operator+=(const Laziness &that) {
if(that.fill)
*this = that;
return *this;
}
void addToVal(Val &val, int) const {
if(fill)
val = expr;
}
void addToSum(Sum &sum, int left, int right) const {
if(fill) {
LinearExpr multiplicated = expr * (right - left);
sum.forward = sum.backward = multiplicated;
}
}
};
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 = 1; 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) {
int indices[128];
int k = getIndices(indices, i, i+1);
propagateRange(indices, k);
return leafs[i];
}
Sum getRangeCommutative(int i, int j) {
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;
}
Sum getRange(int i, int j) {
int indices[128];
int k = getIndices(indices, i, j);
propagateRange(indices, k);
Sum res = Sum();
for(; i && i + (i&-i) <= j; i += i&-i)
res += sum((n+i) / (i&-i));
for(k = 0; i < j; j -= j&-j)
indices[k ++] = (n+j) / (j&-j) - 1;
while(-- k >= 0) res += sum(indices[k]);
return res;
}
void set(int i, const Val &x) {
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;
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[], int i, int j) const {
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 - n);
laziness[i].addToVal(leafs[i * 2 + 1 - n], i * 2 + 1 - n);
}
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);
}
};
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<FenwickTree>??????1??????????
//sortednodes?[lefts[v], rights[v])?v?subtree??????
vector<int> sortednodes, offsets; //Index -> Vertex, Color -> Index
vector<int> lefts, rights; //Vertex -> Index
struct BuildDFSState {
int i, len, parent;
BuildDFSState() { }
BuildDFSState(int i_, int l, int p): i(i_), len(l), parent(p) { }
};
//??????????????????????????
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);
sortednodes.clear(); offsets.clear();
lefts.assign(n, -1); rights.assign(n, -1);
vector<int> subtreesizes;
measure(g, root, subtreesizes);
typedef BuildDFSState State;
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 index = sortednodes.size();
int color = lengths.size();
if(t.parent == -3) {
rights[i] = index;
continue;
}
if(t.parent != -2) {
assert(parents.size() == color);
parents.push_back(t.parent);
branches.push_back(len);
offsets.push_back(index);
len = 0;
}
colors[i] = color;
positions[i] = len;
lefts[i] = index;
sortednodes.push_back(i);
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;
}
s.push_back(State(i, -1, -3));
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));
}
}
}
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;
}
}
}
};
int lowest_common_ancestor(const CentroidPathDecomposition &cpd, int x, int y) {
int cx, px, cy, py;
cpd.get(x, cx, px);
cpd.get(y, cy, py);
while(cx != cy) {
if(cpd.depths[*cpd.nodesBegin(cx)] < cpd.depths[*cpd.nodesBegin(cy)])
cpd.go_up(cy, py);
else
cpd.go_up(cx, px);
}
return cpd.nodesBegin(cx)[min(px, py)];
}
int main() {
int N;
scanf("%d", &N);
vector<Val> initval(N);
rep(i, N) {
int a, b;
scanf("%d%d", &a, &b);
initval[i] = LinearExpr(a, b);
}
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);
}
CentroidPathDecomposition cpd;
cpd.build(g, 0);
vector<Val> permutatedInitval(N);
rep(i, N)
permutatedInitval[i] = initval[cpd.sortednodes[i]];
SegmentTree segt;
segt.init(permutatedInitval);
vector<pii> path;
int Q;
scanf("%d", &Q);
rep(ii, Q) {
int ty;
scanf("%d", &ty);
if(ty == 1) {
int u, v, a, b;
scanf("%d%d%d%d", &u, &v, &a, &b), -- u, -- v;
Laziness laziness(LinearExpr(a, b));
int w = lowest_common_ancestor(cpd, u, v), wc, wp;
cpd.get(w, wc, wp);
rep(uv, 2) {
int c, p;
cpd.get(uv == 0 ? u : v, c, p);
while(1) {
int top = c == wc ? wp + uv : 0;
int o = cpd.offsets[c], len = cpd.lengths[c];
//???[o + top, o + p]????? (????)
segt.addToRange(o + top, o + p + 1, laziness);
if(c == wc) break;
cpd.go_up(c, p);
}
}
}else if(ty == 2) {
int u, v, x;
scanf("%d%d%d", &u, &v, &x), -- u, -- v;
LinearExpr expr;
int w = lowest_common_ancestor(cpd, u, v), wc, wp;
cpd.get(w, wc, wp);
rep(uv, 2) {
path.clear();
int c, p;
cpd.get(uv == 0 ? u : v, c, p);
while(1) {
int top = c == wc ? wp + uv : 0;
int o = cpd.offsets[c], len = cpd.lengths[c];
//???[o + top, o + p]????? (????)
path.push_back(mp(o + top, o + p));
if(c == wc) break;
cpd.go_up(c, p);
}
if(uv == 0) {
for(int i = 0; i < (int)path.size(); ++ i) {
int top = path[i].first, bottom = path[i].second;
expr += segt.getRange(top, bottom + 1).backward;
}
}else {
for(int i = (int)path.size() - 1; i >= 0; -- i) {
int top = path[i].first, bottom = path[i].second;
expr += segt.getRange(top, bottom + 1).forward;
}
}
}
mint ans = expr.evalute(x);
printf("%d\n", ans.get());
}else return 1;
}
return 0;
}
Scor obtinut: 1.0
Submission ID: 464653776
Link challenge: https://www.hackerrank.com/challenges/white-falcon-and-tree/problem