Đăng nhập để hỏi chi tiết
chán quá nên để chơi tìm nhân tài:) có link test mà nhác tìm quái nên cứ cmt đại ở bl cũng dc :v
nnlt: pas, py, c++
Hãy luôn nhớ cảm ơn và vote 5*
nếu câu trả lời hữu ích nhé!
\begin{array}{c} \color{#FFFFFFff}{F}\color{#D0E4FFff}{u}\color{#A4C8FFff}{r}\color{#78ACFFff}{i}\color{#4C90FFff}{n}\color{#2064FFff}{a} \color{#0040A4ff}{F}\color{#2064FFff}{o}\color{#4C90FFff}{r}\color{#78ACFFff}{c}\color{#A4C8FFff}{a}\color{#D0E4FFff}{l}\color{#FFFFFFff}{o}\color{#D0E4FFff}{s} \end{array}
/**
* author: furinaforcalos
* created: 10.05.2025
**/
#include<bits/stdc++.h>
using namespace std;
#define hutao long long
const hutao nmax=200005;
const hutao maxn=20;
vector<hutao> cay[nmax];
hutao beo[nmax];
hutao dp[nmax][maxn];
hutao sonbeo[nmax];
hutao f[nmax];
void dfs(hutao u,hutao p)
{
dp[u][0]=p;
for(hutao i=1;i<maxn;i++)
{
if(dp[u][i-1])
{
dp[u][i]=dp[dp[u][i-1]][i-1];
}
}
for(hutao v:cay[u])
{
if(v!=p)
{
sonbeo[v]=sonbeo[u]+1;
f[v]=f[u]+beo[v];
dfs(v,u);
}
}
}
hutao lca(hutao u,hutao v)
{
if(sonbeo[u]<sonbeo[v])
{
swap(u,v);
}
for(hutao i=maxn-1;i>=0;i--)
{
if(sonbeo[u]-(1<<i)>=sonbeo[v])
{
u=dp[u][i];
}
}
if(u==v)
{
return u;
}
for(hutao i=maxn-1;i>=0;i--)
{
if(dp[u][i]&&dp[u][i]!=dp[v][i])
{
u=dp[u][i];
v=dp[v][i];
}
}
return dp[u][0];
}
bool check(vector<hutao> a,hutao k)
{
unordered_map<hutao,hutao> mp;
hutao tong=0;
mp[0]=-1;
for(hutao i=0;i<a.size();i++)
{
tong+=a[i];
if(mp.count(tong-k))
{
hutao dau=mp[tong-k]+1;
hutao cuoi=i;
if(cuoi-dau+1>=2)return true;
}
if(!mp.count(tong))
{
mp[tong]=i;
}
}
return false;
}
struct st
{
hutao u,v,k;
};
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
hutao q;
cin>>q;
hutao nc=1;
beo[1]=1;
f[1]=1;
sonbeo[1]=0;
vector<st> qu;
for(hutao i=0;i<q;i++)
{
string s;
cin>>s;
if(s=="+")
{
hutao v,x;
cin>>v>>x;
nc++;
beo[nc]=x;
cay[v].push_back(nc);
cay[nc].push_back(v);
}
else
{
hutao u,v,k;
cin>>u>>v>>k;
qu.push_back({u,v,k});
}
}
dfs(1,0);
for(st q:qu)
{
hutao u=q.u;
hutao v=q.v;
hutao k=q.k;
hutao w=lca(u,v);
vector<hutao> m;
hutao ans=u;
while(ans!=w)
{
m.push_back(beo[ans]);
ans=dp[ans][0];
}
m.push_back(beo[w]);
vector<hutao> ve;
ans=v;
while(ans!=w)
{
ve.push_back(beo[ans]);
ans=dp[ans][0];
}
reverse(ve.begin(),ve.end());
for(hutao x:ve)
{
m.push_back(x);
}
if(m.size()>=2&&check(m,k))
{
cout<<"YES\n";
}
else
{
cout<<"NO\n";
}
}
}
Hãy giúp mọi người biết câu trả lời này thế nào?
Bảng tin