#include <cstdio>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
using namespace std;
const int NMAX = 1e5;
struct data_t{
int tree_id;
int st;
int dr;
int father;
bool operator < (const data_t &other)const{
if(tree_id != other.tree_id){
return tree_id < other.tree_id;
}
if(st != other.st){
return st < other.st;
}
if(dr != other.dr){
return dr < other.dr;
}
return father < other.father;
}
};
class SegTree{
int n;
vector <long long> aint;
vector <long long> lazy;
void propag(int nod,int st,int dr){
if(lazy[nod] == 0 || st == dr){
return ;
}
aint[nod * 2] += lazy[nod];
lazy[nod * 2] += lazy[nod];
aint[nod * 2 + 1] += lazy[nod];
lazy[nod * 2 + 1] += lazy[nod];
lazy[nod] = 0;
}
void update(int nod,int st,int dr,int l,int r,long long delta){
propag(nod,st,dr);
if(dr < l || st > r){
return ;
}
if(l <= st && dr <= r){
aint[nod] += delta;
lazy[nod] += delta;
return ;
}
int mid = (st + dr) / 2;
update(nod * 2,st,mid,l,r,delta);
update(nod * 2 + 1,mid + 1,dr,l,r,delta);
aint[nod] = max(aint[nod * 2],aint[nod * 2 + 1]);
}
public:
SegTree(int n){
this->n = n;
aint = vector<long long>(4 * n + 1,0);
lazy = vector<long long>(4 * n + 1,0);
}
void update(int l,int r,long long val){
update(1,1,n,l,r,val);
}
long long query(){
return aint[1];
}
};
int n,q;
long long w;
bool viz[NMAX + 5];
int weight[NMAX + 5];
vector<int> graph[NMAX + 5];
pair<int,int> edge[NMAX + 5];
long long cost[NMAX + 5];
class RootPathSolver{
int lst;
int root;
vector< SegTree > trees;
unordered_map<int,data_t> stuff;
set<pair<long long,int> > answers;//(best path,tree id)
void dfs(int nod,int tata,int id){
data_t tmp = {id,++lst,-1,tata};
weight[nod] = 1;
for(auto it:graph[nod]){
if(it == tata || viz[it] == true){
continue;
}
dfs(it,nod,id);
weight[nod] += weight[it];
}
tmp.dr = lst;
stuff[nod] = tmp;
}
public:
RootPathSolver(){
}
RootPathSolver(int root){
this->root = root;
int lst_id = -1;
for(auto it:graph[root]){
if(viz[it] == false){
lst = 0;
dfs(it,root,++lst_id);
trees.push_back(SegTree(weight[it]));
answers.insert({0,it});
}
}
}
void update(pair<int,int> edge,long long delta){
data_t tmp = stuff[edge.second];
if(edge.second == root || tmp.father != edge.first){
swap(edge.second,edge.first);
tmp = stuff[edge.second];
}
answers.erase({trees[tmp.tree_id].query(),tmp.tree_id});
trees[tmp.tree_id].update(tmp.st,tmp.dr,delta);
answers.insert({trees[tmp.tree_id].query(),tmp.tree_id});
}
long long query(){
if(answers.empty()){
return 0;
}
else if(answers.size() == 1){
return answers.rbegin()->first;
}
else{
return (answers.rbegin())->first + (next(answers.rbegin()))->first;
}
}
};
class Centroid{
public:
int root;
vector<RootPathSolver> chestie;
vector<vector<int> > history;
set<pair<long long,int> > answers;
void dfs(int nod,int tata){
weight[nod] = 1;
for(auto it:graph[nod]){
if(it == tata || viz[it] == true){
continue;
}
dfs(it,nod);
weight[nod] += weight[it];
}
}
void dfs_root(int nod,int tata,int root){
if(root != nod){
history[nod].push_back(root);
}
for(auto it:graph[nod]){
if(viz[it] == true || it == tata){
continue;
}
dfs_root(it,nod,root);
}
}
int centroid(int nod){
dfs(nod,0);
int total_weight = weight[nod];
int root = nod;
while(true){
int bst = -1;
for(auto it:graph[root]){
if(viz[it] == true || it == nod){
continue;
}
if(bst == -1 || weight[it] > weight[bst]){
bst = it;
}
}
if(bst != -1 && weight[bst] * 2 > total_weight){
nod = root;
root = bst;
}
else{
break;
}
}
viz[root] = true;
chestie[root] = RootPathSolver(root);
dfs_root(root,0,root);
answers.insert({0,root});
for(auto it:graph[root]){
if(viz[it] == false){
int tmp = centroid(it);
}
}
return root;
}
public:
Centroid(int n){
this->chestie = vector<RootPathSolver>(n + 1,RootPathSolver());
this->history = vector<vector<int>>(n + 1,vector<int>());;
this->root = centroid(1);
}
void update(pair<int,int> edge,long long delta){
if(history[edge.first].size() > history[edge.second].size()){
swap(edge.first,edge.second);
}
for(auto it:history[edge.second]){
answers.erase({chestie[it].query(),it});
chestie[it].update(edge,delta);
answers.insert({chestie[it].query(),it});
}
}
long long query(){
return answers.rbegin()->first;
}
};
int main(){
scanf("%d %d %lld",&n,&q,&w);
for(int i = 1;i < n;i++){
scanf("%d %d %lld",&edge[i].first,&edge[i].second,&cost[i]);
graph[edge[i].first].push_back(edge[i].second);
graph[edge[i].second].push_back(edge[i].first);
}
Centroid a(n);
for(int i = 1;i < n;i++){
a.update(edge[i],cost[i]);
}
long long last = 0;
while(q--){
int d;
long long e;
scanf("%d %lld",&d,&e);
d = (d + last) % (n - 1) + 1;
e = (e + last) % w;
a.update(edge[d],e - cost[d]);
cost[d] = e;
last = a.query();
printf("%lld\n",last);
}
return 0;
}
Compilation message
diameter.cpp:100:5: error: 'unordered_map' does not name a type
unordered_map<int,data_t> stuff;
^~~~~~~~~~~~~
diameter.cpp: In member function 'void RootPathSolver::dfs(int, int, int)':
diameter.cpp:116:9: error: 'stuff' was not declared in this scope
stuff[nod] = tmp;
^~~~~
diameter.cpp: In member function 'void RootPathSolver::update(std::pair<int, int>, long long int)':
diameter.cpp:138:22: error: 'stuff' was not declared in this scope
data_t tmp = stuff[edge.second];
^~~~~
diameter.cpp: In member function 'int Centroid::centroid(int)':
diameter.cpp:228:21: warning: unused variable 'tmp' [-Wunused-variable]
int tmp = centroid(it);
^~~
diameter.cpp: In function 'int main()':
diameter.cpp:261:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %lld",&n,&q,&w);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~
diameter.cpp:264:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %lld",&edge[i].first,&edge[i].second,&cost[i]);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
diameter.cpp:282:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %lld",&d,&e);
~~~~~^~~~~~~~~~~~~~~~~
