1 solutions

  • 0
    @ 2024-03-29 12:20:49

    Author Code (Kamonasish Roy) :

    #include<bits/stdc++.h>
    using namespace std;
    const long long M=2e5+10,MOD=2000000007;
    typedef long long ll;
    vector<int>edge[M];
    int par[M];
    int pos[1001][1001];
    int counti[10001];
    int vis[10001];
    int maximumlenght[10001];
    void dfs(int x){
    vis[x]=1;
    for(int id:edge[x]){
    if(!vis[id]){
    par[id]=x;
    dfs(id);
    }
    }
    }
    int main()
    {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t=1;
    // cin>>t;
    while(t--){
    int n;
    cin>>n;
    string s;
    cin>>s;
    for(int i=1;i<n;i++){
    int x,y;
    cin>>x>>y;
    edge[x].push_back(y);
    edge[y].push_back(x);
    }
    par[1]=1;
    dfs(1);
    for(int i=1;i<=n;i++){
    vector<int>v;
    v.push_back(i);
    int x=i;
    while(par[x]!=x){
    x=par[x];
    v.push_back(x);
    }
    reverse(v.begin(),v.end());
    int l=1,r=v.size();
    maximumlenght[i]=v.size();
    int cnt=0;
    while(l<=r){
    if(l==r){
    pos[i][v[l-1]]=v[l-1];
    cnt++;
    }
    else{
    if(s[v[l-1]-1]==s[v[r-1]-1]){
    cnt+=2;
    }
    pos[i][v[l-1]]=v[r-1];
    pos[i][v[r-1]]=v[l-1];
    }
    l++;
    r--;
    }
    counti[i]=cnt;

    }
    int q;
    cin>>q;
    while(q--){
        int node;
        char ch;
        cin>>node>>ch;
        int res=1;
        for(int i=1;i<=n;i++){
            int x=pos[i][node];
            if(x>0 && x!=node){
              if(s[node-1]==s[x-1]){
                counti[i]--;
                if(node!=x)counti[i]--;
              }
              if(ch==s[x-1]){
                counti[i]++;
                if(node!=x)counti[i]++;
              }
            }
            if(counti[i]==maximumlenght[i])res=max(res,counti[i]);
        }
        s[node-1]=ch;
        cout<<res<<"\n";
    }

    }
    return 0;
    }

  • 1

Information

ID
1045
Difficulty
9
Category
(None)
Tags
(None)
# Submissions
8
Accepted
3
Accepted Ratio
38%
Uploaded By