Pagini recente » Cod sursa (job #20801) | Cod sursa (job #136171) | Cod sursa (job #2131297) | Cod sursa (job #60480) | Cod sursa (job #3150125)
#include <iostream>
#include <fstream>
#include <vector>
#define nmax 32002
#define logmax 17
using namespace std;
ifstream f("atac.in");
ofstream g("atac.out");
vector<pair<int,int>> V[nmax];
vector<int> solutie;
int n,m,p,x,y,z,a,b,c,d,k,euler[2*nmax],fap[nmax],lvl[nmax],rmq[logmax][nmax],lg[2*nmax],nivele[nmax];
pair<int,int> dp[logmax][nmax];
bool viz[nmax];
void dfs(int x,int lv)
{
viz[x]=true;
nivele[x]=lv;
euler[++k]=x;
lvl[k]=lv;
fap[x]=k;
for(auto a:V[x])
{
if(!viz[a.first])
{
dp[0][a.first].first=x;
dp[0][a.first].second=a.second;
dfs(a.first,lv+1);
euler[++k]=x;
lvl[k]=lv;
}
}
}
void compute_rmq()
{
lg[1]=0;
for(int i=2;i<=k;i++)
lg[i]=lg[i>>1]+1;
for(int i=1;i<=k;i++)
rmq[0][i]=i;
for(int i=1;i<=lg[k];i++)
{
for(int j=1;j+(1<<i)-1<=k;j++)
{
rmq[i][j]=lvl[rmq[i-1][j]]<lvl[rmq[i-1][j+(1<<(i-1))]]?rmq[i-1][j]:rmq[i-1][j+(1<<(i-1))];
}
}
}
int lca(int x,int y)
{
int st=fap[x],dr=fap[y];
if(st>dr)
swap(st,dr);
int lin=lg[dr-st+1];
int ans=lvl[rmq[lin][st]]<lvl[rmq[lin][dr-(1<<lin)+1]]?rmq[lin][st]:rmq[lin][dr-(1<<lin)+1];
return euler[ans];
}
void compute_dp()
{
for(int i=1;i<=lg[n];i++)
{
for(int j=1;j<=n;j++)
{
dp[i][j].first=dp[i-1][dp[i-1][j].first].first;
dp[i][j].second=min(dp[i-1][j].second,dp[i-1][dp[i-1][j].first].second);
}
}
}
int ans(int x,int y)
{
int niv=nivele[x]-nivele[y],curr=x;
int ans=0x3f3f3f3f;
for(int i=0;(1<<i)<=niv;i++)
{
if(niv&(1<<i))
{
ans=min(ans,dp[i][curr].second);
curr=dp[i][curr].first;
}
}
return ans;
}
int main() {
f >> n >> m >> p;
for (int i = 2; i <= n; i++) {
int u, v;
f >> u >> v;
V[u].push_back(make_pair(i, v));
V[i].push_back(make_pair(u, v));
}
dfs(1, 0);
compute_rmq();
compute_dp();
f>>x>>y>>a>>b>>c>>d;
int z;
int lc=lca(x,y);
z=min(ans(x,lc),ans(y,lc));
solutie.push_back(z);
for(int i=2;i<=m;i++)
{
int x1=(x*a+y*b)%n+1;
int y1=(y*c+z*d)%n+1;
int lc=lca(x1,y1);
z=min(ans(x1,lc),ans(y1,lc));
solutie.push_back(z);
x=x1;
y=y1;
}
for(int i=p-1;i<solutie.size();i++)
g<<solutie[i]<<'\n';
return 0;
}