1 solutions
-
0Bullet LV 4 MOD @ 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