PROBLEM LINK:
Author: Sandeep Singh
Tester: Arnab Chanda
Editorialist: Sandeep SIngh
DIFFICULTY:
MEDIUM - HARD
PREREQUISITES:
BIT/Segment Tree, LCA, Euler Tour on trees, Sorting
EXPLANATION:
Quick Explanation:
Sort the queries and the values in the ascending order. We will solve queries offline. Do an ETT over the tree and calculate IN and OUT for each node. We will use BIT to answer queries.
Initially, all nodes are 0. Let’s Answer the query in ascending order.
For each query, all nodes with value less than equal to w of that query are added to the BIT( positive value at IN of that node and negative value at OUT). After no such nodes are left, We can answer the query. Bit query of IN[u] will give us summation over node 1 to u. Note that we have only added values less than W of the current query. Use LCA and some basic maths to answer the query.
Detalied explanation:
To be updated.
SOLUTIONS:
Setter's Solution
//What a drag
#include <bits/stdc++.h>
#define int long long
#define ll long long
#define max(a,b) (a>b?a:b)
#define min(a,b) (a<b?a:b)
#define ln cout << '\n'
#define pi pair<int, int>
#define mod 1000000007
#define MxN 100005
#define level 20
#define all(x) x.begin(), x.end()
using namespace std;
vector<int> G[MxN];
int parent[MxN][level], depth[MxN];
vector<int> in(MxN),out(MxN), qu(MxN), qv(MxN);
int tme = 0;
int n, nn;
int bt[3 * MxN];
void upd(int i, int x) {
for(++i; i<=nn+1; i+=i&-i)
bt[i]+=x;
}
int qry(int i) {
i = i + 1;
int r=0;
for(; i; i-=i&-i)
r+=bt[i];
return r;
}
void dfs(int u, int p) {
in[u] = tme++;
depth[u] = depth[p] + 1;
parent[u][0] = p;
for(int child: G[u]){
if(child != p)
dfs(child,u);
}
out[u] = tme++;
}
void precomputeSparseMatrix() {
for (int i=1; i<level; i++) {
for (int node = 1; node <= n; node++) {
if (parent[node][i-1] != -1)
parent[node][i] =
parent[parent[node][i-1]][i-1];
}
}
}
int lca(int u, int v) {
if (depth[v] < depth[u])
swap(u, v);
int diff = depth[v] - depth[u];
for (int i=0; i<level; i++)
if ((diff>>i)&1)
v = parent[v][i];
if (u == v)
return u;
for (int i=level-1; i>=0; i--)
if (parent[u][i] != parent[v][i]) {
u = parent[u][i];
v = parent[v][i];
}
return parent[u][0];
}
void solve(){
int i, j, q;
cin >> n >> q;
nn = 2 * n;
vector <int> ans(q, 0);
memset(parent,-1,sizeof(parent));
for(i = 0; i < n - 1; ++i){
int u, v;
cin >> u >> v;
G[u].push_back(v);
G[v].push_back(u);
}
dfs(1, 0);
precomputeSparseMatrix();
vector<pair<int, int>> vals(n);
vector <int> nums(n + 1, 0);
vector<pi> qq(q);
for(i = 0; i < n; ++i){
int tmp;
cin >> tmp;
vals[i] = {tmp, i + 1};
}
for(i = 0;i < q; ++i){
int w;
cin >> qu[i] >> qv[i] >> w;
qq[i] = {w, i};
}
sort(all(qq));
sort(all(vals));
int ctr = 0;
for(i = 0; i < q; ++i){
int idx = qq[i].second, wt = qq[i].first;
int u = qu[idx], v = qv[idx], lc = lca(u, v);
while(ctr < n && vals[ctr].first <= wt){
int num = vals[ctr].first, pos = vals[ctr].second;
upd(in[pos], num);
upd(out[pos], -1 * num);
nums[pos] = num;
++ctr;
}
ans[idx] = qry(in[u]) + qry(in[v]) - 2 * qry(in[lc]);
ans[idx] += nums[lc];
}
for(int x : ans)
cout << x << "\n";
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);cout.tie(NULL);
#ifndef ONLINE_JUDGE
freopen("input.txt","r",stdin);
#endif
int t = 1;
//cin >> t;
while(t--)
solve();
}