Pagini recente » Cod sursa (job #953060) | Rating Stoican Dragos (dago28) | Cod sursa (job #97430) | Cod sursa (job #1211879) | Cod sursa (job #730768)
Cod sursa(job #730768)
#include <fstream>
#include <vector>
using namespace std;
const int N=32005,M=3000009,LG=16,inf=1<<30;
int T[LG][N],C[LG][N],depth[N],n,m,k,A,B,c,D,dim=-1;
bool use[N];
char PRINT[M];
struct Muchie
{
int x,c;
};
vector<Muchie> a[N];
ifstream in("atac.in");
ofstream out("atac.out");
void push(int x)
{
if (x<10)
{
PRINT[++dim]=x+'0';
return;
}
push(x/10);
PRINT[++dim]=x%10+'0';
}
inline void next(int &x,int &y,int z)
{
x=(A*x+B*y)%n+1;
y=(c*y+D*z)%n+1;
}
int tata(int x,int L)
{
for (int i=LG-1;i>=0;i--)
if ((1<<i)<=L)
{
x=T[i][x];
L-=1<<i;
}
return x;
}
int cost(int x,int L)
{
int rez=inf;
for (int i=LG-1;i>=0;i--)
if ((1<<i)<=L)
{
rez=min(rez,C[i][x]);
x=T[i][x];
L-=1<<i;
}
return rez;
}
int lca(int x,int y)
{
if (depth[x]<depth[y])
y=tata(y,depth[y]-depth[x]);
if (depth[x]>depth[y])
x=tata(x,depth[x]-depth[y]);
if (x==y)
return x;
for (int i=LG-1;i>=0;i--)
if (T[i][x] && T[i][y] && T[i][x]!=T[i][y])
{
x=T[i][x];
y=T[i][y];
}
return T[0][x];
}
void dfs(int x)
{
int y,c;
use[x]=true;
for (vector<Muchie>::iterator i=a[x].begin();i!=a[x].end();i++)
{
y=(*i).x;
c=(*i).c;
if (!use[y])
{
T[0][y]=x;
C[0][y]=c;
depth[y]=depth[x]+1;
dfs(y);
}
}
}
int main()
{
int x,y,L,rez;
in>>n>>m>>k;
for (x=2;x<=n;x++)
{
in>>y>>c;
a[x].push_back((Muchie){y,c});
a[y].push_back((Muchie){x,c});
}
in>>x>>y>>A>>B>>c>>D;
A%=n;B%=n;c%=n;D%=n;
dfs(1);
for (int i=1;i<LG;i++)
for (int j=1;j<=n;j++)
{
T[i][j]=T[i-1][T[i-1][j]];
if (!T[i][j])
C[i][j]=inf;
else
C[i][j]=min(C[i-1][j],C[i-1][T[i-1][j]]);
}
for (int i=1;i<=m;i++)
{
if (x!=y)
{
L=depth[lca(x,y)];
rez=min(cost(x,depth[x]-L),cost(y,depth[y]-L));
}
else
rez=0;
next(x,y,rez);
if (m-k<i)
{
push(rez);
PRINT[++dim]='\n';
}
}
out<<PRINT;
return 0;
}