Pagini recente » Cod sursa (job #997540) | Cod sursa (job #1376970) | Cod sursa (job #1002587) | Cod sursa (job #3313221) | Cod sursa (job #3326969)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("atac.in");
ofstream fout("atac.out");
const int EMAX=15, NMAX=32e3+1, INF=1e5+1;
int n, m, p, x, y, z, a, b, c, d;
int lg[NMAX], dp[EMAX][NMAX], t[EMAX][NMAX], lvl[NMAX];
vector <pair <int,int>> g[NMAX];
bitset <NMAX> viz;
void dfs(int x, int h){
viz[x]=1;
lvl[x]=h;
for(auto vec : g[x]){
if(!viz[vec.first]){
t[0][vec.first]=x;
dp[0][vec.first]=vec.second;
dfs(vec.first, h+1);
}
}
}
int anc(int nod, int ord){
int e = 0;
while(ord){
if(ord%2){
z=min(z, dp[e][nod]);
nod=t[e][nod];
}
ord/=2;
e++;
}
return nod;
}
int lca(int x, int y){
int e=lg[lvl[x]];
while(e>=0){
if(t[e][x]!=t[e][y]){
z=min(z, dp[e][x]);
z=min(z, dp[e][y]);
x=t[e][x];
y=t[e][y];
}
e--;
}
z=min(z, dp[0][x]);
z=min(z, dp[0][y]);
return t[0][x];
}
int main(){
fin>>n>>m>>p;
for(int i=2;i<=n;i++){
fin>>x>>y;
g[x].push_back({i,y});
g[i].push_back({x,y});
//t[0][i]=x;
//dp[0][i]=y;
}
fin>>x>>y>>a>>b>>c>>d;
for(int i=2;i<=n;i++){
lg[i]=lg[i/2]+1;
}
dfs(1, 1);
for(int e=1;e<=lg[n];e++){
//cout<<e<<endl;
for(int i=1;i<=n;i++){
t[e][i]=t[e-1][t[e-1][i]];
dp[e][i]=min(dp[e-1][i], dp[e-1][t[e-1][i]]);
//cout<<i<<' '<<t[e][i]<<' '<<dp[e][i]<<endl;
}
}
while(m--){
z=INF;
if(y==x)
z=0;
if(lvl[x]>lvl[y])
swap(x,y);
y=anc(y, lvl[y]-lvl[x]);
lca(y, x);
if(m<p)
fout<<z<<'\n';
x=(a*x+b*y)%n+1;
y=(c*y+d*z)%n+1;
}
return 0;
}