pastemyst | lucas numbers test1

lucas numbers test1

lucas

C++copy raw

// ver coigos de : 
//|https://codeforces.com/contest/2006/problem/E

#include <cstdio>
#include <vector>
#include <algorithm>
#include <ostream>
typedef long long ll; 
typedef unsigned  u32;
const int INF = 1e9;  
//const int MOD = 1e9 + 7;
const int N = 1e5 + 7;

template<u32 MOD>
struct Modular_Integer{
    ll value;
    using mod = Modular_Integer;
    Modular_Integer(ll v = 0) {
        value = v % MOD;
        if (value < 0) value += MOD;
    }
 
    mod& operator+=(const mod& other) {
        value += other.value;
        if (value >= MOD) value -= MOD;
        return *this;
    }
 
    mod& operator-=(const Modular_Integer& other) {
        value -= other.value;
        if (value < 0) value += MOD;
        return *this;
    }
 
    mod& operator*=(const Modular_Integer& other) {
        value = value * other.value % MOD;
        return *this;
    }
 
    mod& operator/=(const Modular_Integer& other) {
        return *this *= other.inv(); 
    }
 
    mod operator-() const {
        return mod(-value);
    }
 
    mod inv() const {
        return binpow(MOD - 2);
    }
    mod binpow(ll exp) const {
        mod result = 1;
        mod base = value;
        while (exp) {
            if (exp % 2) result *= base;
            base *= base;
            exp>>=1;
        }
        return result;
    }
 
    friend mod operator+(mod a, const mod& b) { return a += b; }
    friend mod operator-(mod a, const mod& b) { return a -= b; }
    friend mod operator*(mod a, const mod& b) { return a *= b; }
    friend mod operator/(mod a, const mod& b) { return a /= b; }
 
    friend std::ostream& operator<<(std::ostream& os, const mod& m) {
        return os << m.value;
    }
};

const u32 MOD = 1e9+7;
using Mint=Modular_Integer<MOD>;

std::vector<std::pair<int, int>> G[N];  
std::vector<std::pair<int, int>> edges; 
int cnt = 0,n,fa[N], deep[N], sz[N], head[N], son[N], pos[N], lucas[N];

void Precomp(){
    lucas[1] = 3; 
    lucas[2] = 4; 
    for (int i = 3; i < N; i++) {
        lucas[i] = (lucas[i - 1] + lucas[i - 2]) % MOD;
    }
}

int seg[N];
struct Node{   
    Mint sum; 
    ll lazyVal; 
    bool haslazy;
};
 
 
Node tree[N];

#define left  node << 1 
#define right  node<< 1 | 1

void merge(int node){
    tree[node].sum = tree[left].sum + tree[right].sum;
}

void init(int node, int nl ,int nr){
    if(nl == nr){
        tree[node].sum = seg[nl];
        return; 
    }
    int mid = (nl + nr) >> 1;
    init(left,nl, mid);
    init(right, mid + 1, nr);
    merge(node);
}
 
 
void apply(int node, int l, int r, ll val){
    tree[node].sum += val * (r - l + 1);
    tree[node].lazyVal += val;
    tree[node].haslazy = true;
}
 
void propagate(int node, int l ,int r){
    if(tree[node].haslazy){
        int mid = (l + r) >> 1; 
        apply(left, l, mid, tree[node].lazyVal);
        apply(right,  mid + 1, r, tree[node].lazyVal);
        tree[node].haslazy = false; 
        tree[node].lazyVal = 0;
    }
}
 
void updateST(int node, int nl, int nr, int ql ,int qr, ll val){
    if(nr < ql || nl > qr) return;
    if(ql <= nl && nr <= qr){
        apply(node,nl,nr,val);
        return;
    }
    propagate(node,nl,nr);
    int mid = (nl + nr) >> 1; 
    updateST(left, nl, mid, ql, qr, val);
    updateST(right, mid + 1,nr, ql ,qr, val);
    merge(node);
        
}
void updateST(int l ,int r , ll val){
    updateST(1,0,n-1,l,r,val);
}
Mint queryST(int node, int nl ,int nr, int ql, int qr){
    if(nr < ql || nl > qr) return 0LL;
    if(ql <= nl && nr <= qr){
        return tree[node].sum;
    }
    propagate(node, nl ,nr);
 
    int mid = (nl + nr)>>1;
    Mint iz = queryST(left, nl , mid,ql,qr);
    Mint de = queryST(right , mid + 1, nr, ql,qr);
    return iz + de;
}   
 
Mint queryST(int l ,int r){
    return queryST(1, 0 ,n-1,l,r);
}

void Dfs(int node, int d, int father) {
    sz[node] = 1;
    deep[node] = d;
    fa[node] = father;
    int mx = 0; 
    for (auto &u : G[node]) {
        if (u.first == father) continue;
        Dfs(u.first, d + 1, node);
        sz[node] += sz[u.first];
        if (sz[u.first] > mx) {
            mx = sz[u.first];
            son[node] = u.first;
        }
    }
}
void HLD(int node, int w, int prev) {
    head[node] = prev;
    pos[node] = cnt++;
    seg[pos[node]] = w;
    if (son[node]) {
        for (auto &u : G[node]) {
            if (u.first == son[node]) {
                HLD(u.first, u.second, prev);
                break;
            }
        }
    }
    for (auto &u : G[node]) {
        if (u.first != fa[node] && u.first != son[node]) {
            HLD(u.first, u.second, u.first);
        }
    }
}
// LCA using HLD
int LCA(int u, int v) {
    while (head[u] != head[v]) {
        if (deep[head[u]] > deep[head[v]]) {
            u = fa[head[u]];
        } else {
            v = fa[head[v]];
        }
    }
    return (deep[u] < deep[v]) ? u : v;
}

//Mint queryHLD(int u, int v) {
//    Mint res = 0;
//    int lca = LCA(u, v);
//    
//    // Query u to LCA
//    while (head[u] != head[lca]) {
//        res += queryST(pos[head[u]], pos[u]);
//        u = fa[head[u]];
//    }
//    res += queryST(pos[lca], pos[u]);
//
//    // Query v to LCA
//    while (head[v] != head[lca]) {
//        res += queryST(pos[head[v]], pos[v]);
//        v = fa[head[v]];
//    }
//    if (lca != v) {
//        res += queryST(pos[lca] + 1, pos[v]);
//    }
//
//    return res;
//}

Mint queryHLD(int u, int v) {
    Mint res = 0;
    while (head[u] != head[v]) {
        if (deep[head[u]] > deep[head[v]]) std::swap(u, v);
        res = (res + queryST(pos[head[v]], pos[v])) ;
        v = fa[head[v]];
    }
    if (u != v) {
        if (deep[u] > deep[v]) std::swap(u, v);
        res = (res + queryST(pos[u] + 1, pos[v])) ;
    }
    return res;
}

void updateHLD(int u, int v) {
    int idx = 0;  
    while (head[u] != head[v]) {
        if (deep[head[u]] > deep[head[v]]) std::swap(u, v);
        int num_nodos = pos[v] - pos[head[v]] + 1; 
        for (int i = 0; i < num_nodos; ++i) {
            updateST(pos[head[v]] + i, pos[head[v]] + i, lucas[++idx]);
        }
        v = fa[head[v]];  // volvemos
    }
    if (u != v) {
        if (deep[u] > deep[v]) std::swap(u, v);
        int num_nodos = pos[v] - pos[u]; 
        for (int i = 1; i <= num_nodos; ++i) {
            updateST(pos[u] + i, pos[u] + i, lucas[++idx]);
        }
    }
}

void solve() {
    scanf("%d", &n);
    for (int i = 1; i < n; i++) {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        G[u].push_back({v, w});
        G[v].push_back({u, w});
        edges.push_back({u, v});
    }

Dfs(1, 0, 0);
    HLD(1, 0, 1);
    init(1, 0, n - 1);  
    //printf("segtree init\n");
   // for(int i = 0;i<20;i++){
   //     printf("%lld ",tree[i].sum.value);
   // }
    printf("\n");
    int Q;
    scanf("%d", &Q);
    while (Q--) {
        int t, a, b;
        scanf("%d%d%d", &t, &a, &b);
        if (t == 1) {
            printf("%lld\n", queryHLD(a, b).value);
        } else if (t == 2) {
            updateHLD(a, b);
            //for(int i = 0;i<20;i++){
            //    printf("%lld ",tree[i].sum.value);
            //}
            //printf("\n");
        }
    }
}

int main() {
    Precomp();
    int t = 1;
    //scanf("%d", &t);
    while (t--) {
        solve();
    }
    return 0;
}

created at:

stats: 328 lines, 1061 words, 7.32kb