Submission #1303027

#TimeUsernameProblemLanguageResultExecution timeMemory
1303027Muhammad_AneeqDynamic Diameter (CEOI19_diameter)C++20
42 / 100
5092 ms15044 KiB
#include <bits/stdc++.h>
using namespace std;
#define int long long
int const N=1e5+10;
vector<pair<int,int>>nei[N]={};
int dp[N][2]={};
int h[N]={};
int P[N]={};
int mx[N]={};
multiset<int>ans;
void dfs(int u,int p=-1)
{
    P[u]=p;
    for (auto [i,w]:nei[u])
    {
        if (i==p) continue;
        h[i]=h[u]+1;
        dfs(i,u);
        mx[u]=max(mx[u],mx[i]);
        if (dp[u][0]<dp[i][0]+w)
        {
            dp[u][1]=dp[u][0];
            dp[u][0]=dp[i][0]+w;
        }
        else if (dp[u][1]<dp[i][0]+w)
            dp[u][1]=dp[i][0]+w;
    }
    mx[u]=max(mx[u],dp[u][0]+dp[u][1]);
}
void bt(int u)
{
    if (u==-1)
        return;
    dp[u][0]=dp[u][1]=0;
    mx[u]=0;
    for (auto [i,w]:nei[u])
    {
        if (i==P[u]) continue;
        mx[u]=max(mx[u],mx[i]);
        if (dp[u][0]<dp[i][0]+w)
        {
            dp[u][1]=dp[u][0];
            dp[u][0]=dp[i][0]+w;
        }
        else if (dp[u][1]<dp[i][0]+w)
            dp[u][1]=dp[i][0]+w;
    }
    mx[u]=max(mx[u],dp[u][0]+dp[u][1]);
    bt(P[u]);
}
inline void solve()
{
	int n,q,w;
	cin>>n>>q>>w;
    vector<pair<int,int>>ed;
    for (int i=0;i<n-1;i++)
    {
        int u,v,w;
        cin>>u>>v>>w;
        nei[u].push_back({v,w});
        nei[v].push_back({u,w});
        ed.push_back({u,v});
    }
    dfs(1);
    for (auto& [i,j]:ed)
    {
        if (h[i]>h[j])
            swap(i,j);
    }
    int lst=0;
    while (q--)
    {
        int d,e;
        cin>>d>>e;
        d=(d+lst)%(n-1);
        e=(e+lst)%w;
        int z=ed[d].first;
        for (auto& [i,w]:nei[z])
        {
            if (i==ed[d].second)
            {
                w=e;
                break;
            }
        }
        bt(z);
        lst=mx[1];
        cout<<lst<<'\n';
    }
}
signed main()
{
    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
    int t=1;
    for (int i=1;i<=t;i++)
    {
        solve();
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...