Pagini recente » Cod sursa (job #1933664) | Profil camaras | Cod sursa (job #1445914) | Cod sursa (job #1600943) | Cod sursa (job #974263)
Cod sursa(job #974263)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#define newn a[x][i].second
#define cost a[x][i].first;
using namespace std;
ifstream fin("atac.in");
ofstream fout("atac.out");
const int N = 32010;
const int E = N * 2;
const int L = 17;
int n, m, p, nr, A, B, C, D, X, Y, Z, t[N], dt[N],
first[N], euler[E], height[E], lg[E], rmq[L][E];
typedef pair <int, int> nod;
vector <nod> a[N];
vector <bool> viz(N);
void dfs(int x, int level)
{
++nr;
viz[x] = 1;
euler[nr] = x;
height[nr] = level;
first[x] = nr;
for(unsigned i=0; i<a[x].size(); i++)
if(!viz[newn])
{
dfs(newn, level+1);
t[newn] = x;
dt[newn] = cost;
++nr;
euler[nr] = x;
height[nr] = level;
}
}
void Rmq()
{
for(int i=2; i<=nr; i++)
lg[i] = lg[i>>1] + 1;
for(int i=1; i<=nr; i++)
rmq[0][i] = i;
for(int i=1; (1<<i) <= nr; i++)
for(int j=1; j <= nr - (1<<i); j++)
{
const int l = 1 << (i-1);
rmq[i][j] = rmq[i-1][j];
if(height[rmq[i][j]] > height[rmq[i-1][j+l]])
rmq[i][j] = rmq[i-1][j+l];
}
}
void LCA(int x, int y)
{
int xx = x, yy = y, lca, min1, min2;
x = first[x], y = first[y];
if(x > y) swap(x, y);
const int l = lg[y-x+1];
int poz = rmq[l][x];
if(height[poz] > height[rmq[l][y-(1<<l)+1]])
poz = rmq[l][y-(1<<l)+1];
lca = euler[poz];
min1 = min2 = 100005;
//cout<<xx<<' '<<yy<<' '<<lca<<' ';
for(int i=xx; i!=lca; i=t[i])
if(min1 > dt[i]) min1 = dt[i];
for(int i=yy; i!=lca; i=t[i])
if(min2 > dt[i]) min2 = dt[i];
Z = min(min1, min2);
//cout<<Z<<endl;
}
int main()
{
fin>>n>>m>>p;
for(int i=2; i<=n; i++)
{
int x, y;
fin>>x>>y;
a[x].push_back(nod(y, i));
a[i].push_back(nod(y, x));
}
fin>>X>>Y>>A>>B>>C>>D;
dfs(1, 0);
Rmq();
while(m--)
{
LCA(X, Y);
X = (X*A + Y*B) % n + 1;
Y = (Y*C + Z*D) % n + 1;
if(m < p) fout<<Z<<'\n';
}
return 0;
}