Submission #1183983

#	Time	Username	Problem	Language	Result	Execution time	Memory
1183983		kim	Dynamic Diameter (CEOI19_diameter)	C++20	100 / 100	176 ms	30244 KiB

diameter

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
using pii=pair<int,int>;
#define f first
#define s second
#define eb emplace_back
#define sz(x) (int)x.size()
#define add(x,y) ((((x)+(y))%md+md)%md)
#define Add(x,y) (x=add(x,y))
#define mul(x,y) ((((x)*(y))%md+md)%md)
#define Mul(x,y) (x=mul(x,y))
template<class T> T chmn(T &x,T y){ return x=min(x,y); }
template<class T> T chmx(T &x,T y){ return x=max(x,y); }
const int inf=1e9;
const ll linf=1e18;
const ll md=1e9+7;
// const ll md=119<<23|1;

vector<pii> adj[100005];

struct Stt{
  int P[400005],L[400005],R[400005],T[400005],n,rt;
  int hld(int u,int p){
    int su=1,mx=0;
    for(auto &v:adj[u]) if(v.f!=p){
      int sv=hld(v.f,u);
      su+=sv;
      if(mx<sv) mx=sv, swap(v,adj[u][0]);
    }
    for(auto &v:adj[u]) if(v.f==p){
      swap(v,adj[u].back());
      adj[u].pop_back();
      break;
    }
    return su;
  }
  void build(int u){
    n=hld(u,u);
    for(int i=n<<2;i>=0;--i) P[i]=L[i]=R[i]=-1;
    rt=compress(u);
  }
  int node(int u,int l,int r,int t){
    if(u==-1) u=++n;
    if(l!=-1) P[l]=u;
    if(r!=-1) P[r]=u;
    P[u]=-1, L[u]=l, R[u]=r, T[u]=t;
    return u;
  }
  int compress(int u){
    vector<int> chs{add_node(u)};
    while(!adj[u].empty()) chs.eb(add_node(u=adj[u][0].f));
    return merge(chs,4);
  }
  int add_node(int u){
    int v=rake(u);
    return node(u,v,-1,v==-1 ? 0 : 3);
  }
  int rake(int u){
    vector<int> chs;
    for(int i=1;i<sz(adj[u]);++i) chs.eb(add_edge(adj[u][i].f));
    if(chs.empty()) return -1;
    return merge(chs, 2);
  }
  int add_edge(int u){
    int v=compress(u);
    u=node(-1,v,-1,1);
    return u;
  }
  int merge(vector<int> &chs,int t){
    if(sz(chs)==1) return chs[0];
    vector<int> chl,chr;
    for(int i=0;i<sz(chs)>>1;++i) chl.eb(chs[i]);
    for(int i=sz(chs)>>1;i<sz(chs);++i) chr.eb(chs[i]);
    int l=merge(chl,t), r=merge(chr,t);
    int u=node(-1,l,r,t);
    return u;
  }
}stt;

int pa[100005],ch[100005];
ll w_[100005],w[100005],dp[400005][5];

void dfs(int u,int p){
  for(auto &[v,vi]:adj[u]) if(v!=p){
    ch[vi]=v, pa[vi]=u;
    w[v]=w_[vi];
    dfs(v,u);
  }
}
void calc(int u){
  int l=stt.L[u], r=stt.R[u];
  if(stt.T[u]==0){ // node
    dp[u][0]=dp[u][1]=0;
    dp[u][2]=dp[u][3]=w[u];
  }
  else if(stt.T[u]==1){ // add_edge
    dp[u][0]=max(dp[l][0],dp[l][2]);
    dp[u][1]=dp[l][2];
  }
  else if(stt.T[u]==2){ // rake
    dp[u][0]=max({dp[l][0],dp[r][0],dp[l][1]+dp[r][1]});
    dp[u][1]=max(dp[l][1],dp[r][1]);
  }
  else if(stt.T[u]==3){ // add_node
    dp[u][0]=dp[l][0];
    dp[u][1]=dp[l][1];
    dp[u][2]=dp[l][1]+w[u];
    dp[u][3]=w[u];
  }
  else{ // compress
    dp[u][0]=max({dp[l][0],dp[r][0],dp[l][1]+dp[r][2]});
    dp[u][1]=max(dp[r][1],dp[r][3]+dp[l][1]);
    dp[u][2]=max(dp[l][2],dp[l][3]+dp[r][2]);
    dp[u][3]=dp[l][3]+dp[r][3];
  }
}
void pre_calc(int u){
  if(stt.L[u]!=-1) pre_calc(stt.L[u]);
  if(stt.R[u]!=-1) pre_calc(stt.R[u]);
  calc(u);
}

void solve(){
  ll n,Q,mxw; cin>>n>>Q>>mxw;
  for(int i=0;i<n-1;++i){
    int u,v; cin>>u>>v>>w_[i];
    adj[u].eb(v,i), adj[v].eb(u,i);
  }
  dfs(1,1);
  stt.build(1);
  pre_calc(stt.rt);
  ll last=0;
  while(Q--){
    ll d,e; cin>>d>>e;
    d=(d+last)%(n-1);
    e=(e+last)%mxw;
    w[ch[d]]=e;
    for(int i=ch[d];i!=-1;i=stt.P[i]) calc(i);
    cout<<(last=dp[stt.rt][0])<<'\n';
  }
}

int main(){
  ios::sync_with_stdio(false); cin.tie(0);

  int Q(1);
  // cin>>Q;
  while(Q--) solve();  

}
/*

4 3 2000
1 2 100
2 3 1000
2 4 1000
2 1030
1 1020
1 890

10 10 10000
1 9 1241
5 6 1630
10 5 1630
2 6 853
10 1 511
5 3 760
8 3 1076
4 10 1483
7 10 40
8 2051
5 6294
5 4168
7 1861
0 5244
6 5156
3 3001
8 5267
5 3102
8 3623

*/

• Subtask 1: 11 / 11
• Subtask 2: 13 / 13
• Subtask 3: 7 / 7
• Subtask 4: 18 / 18
• Subtask 5: 24 / 24
• Subtask 6: 27 / 27