Pagini recente » Cod sursa (job #309461) | Cod sursa (job #1861115) | Cod sursa (job #2706809) | Cod sursa (job #2265449) | Cod sursa (job #2644332)
#include <bits/stdc++.h>
using namespace std;
ifstream fin ("atac.in");
ofstream fout ("atac.out");
struct drum
{
int x, val;
drum(int x, int val)
{
this->x=x;
this->val=val;
}
};
struct nodS
{
int h=0;
int prev[18];
int premin[18];
vector<drum> vecini;
};
int n,m,p,x,y,ans,a,b,c,d,i,val,lca;
nodS nod[32005];
void dfs(int p, int par, int lval)
{
nod[p].h=nod[par].h+1;
if(p!=1)
{
nod[p].prev[0]=par;
nod[p].premin[0]=lval;
for(int i=1;i<=15;i++)
{
nod[p].prev[i]=nod[nod[p].prev[i-1]].prev[i-1];
if(nod[p].prev[i]==0)
break;
nod[p].premin[i]=min(nod[p].premin[i-1], nod[nod[p].prev[i-1]].premin[i-1]);
}
}
for(auto it : nod[p].vecini)
{
if(it.x!=par)
dfs(it.x, p, it.val);
}
}
int anc(int p, int val)
{
for(int i=0;i<=15;i++)
{
if((val>>i)&1)
{
p=nod[p].prev[i];
}
}
return p;
}
int ancmin(int p, int val)
{
int ans=1e6;
for(int i=0;i<=15;i++)
{
if((val>>i)&1)
{
ans=min(ans, nod[p].premin[i]);
p=nod[p].prev[i];
}
}
return ans;
}
int flca(int x, int y)
{
if(nod[x].h>nod[y].h)
swap(x, y);
y=anc(y, nod[y].h-nod[x].h);
if(x==y)
return x;
for(int i=15;i>=0;i--)
{
if(nod[x].prev[i]!=nod[y].prev[i])
{
x=nod[x].prev[i];
y=nod[y].prev[i];
}
}
return nod[x].prev[0];
}
int main()
{
fin>>n>>m>>p;
for(i=2;i<=n;i++)
{
fin>>x>>val;
nod[x].vecini.push_back(drum(i, val));
nod[i].vecini.push_back(drum(x, val));
}
dfs(1, 0, 0);
fin>>x>>y>>a>>b>>c>>d;
while(m)
{
ans=0;
if(x!=y)
{
lca=flca(x, y);
if(x==lca)
ans=ancmin(y, nod[y].h-nod[lca].h);
else if(y==lca)
ans=ancmin(x, nod[x].h-nod[lca].h);
else
{
ans=min(ancmin(x, nod[x].h-nod[lca].h), ancmin(y, nod[y].h-nod[lca].h));
}
}
if(m<=p)
fout<<ans<<'\n';
//cout<<x<<' '<<y<<' '<<lca<<' '<<ans<<'\n';
x=(x*a + y*b)%n +1;
y=(y*c + ans*d)%n +1;
m--;
}
return 0;
}