Cerinta completa
White Falcon has a tree with nodes. Each node contains a linear function. Let’s denote by the linear function contained in the node .
Let’s denote the path from node to node like this: , where and , and and are connected.
White Falcon also has queries. They are in the following format:
-
. Assign as the function of all the nodes on the path from to , i.e., is changed to where is the path from to .
-
. Calculate modulo
Input Format
The first line contains , the number of nodes. The following lines each contain two integers and that describe the function .
Following lines contain edges of the tree.
The next line contains , 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
(Number of nodes)
(Number of queries)
Sample Input
2
1 1
1 2
1 2
2
1 2 2 1 1
2 1 2 1
Sample Output
3
Explanation
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
White Falcon And Tree