#include <bits/stdc++.h>
using namespace std;
const long long int maxn = 1e5 + 100;
long long int n;
long long int k;
bool mark1[maxn], markl[maxn], isc[maxn];
long long int nxt[maxn], hms, h[maxn], cl, vu[maxn], cycid[maxn], lp, dist[maxn], htl[maxn], mxhu[maxn];
long long int ans[maxn], dif[maxn];
vector <long long int> divs[maxn * 2], ne[maxn];
queue <long long int> bfs;
long long int dis[maxn], id[maxn], csv;
struct Node
{
long long int f[2 * maxn];
vector <pair <long long int, long long int>> h;
bool add;
void init()
{
for (long long int i = 0;i < 2 * maxn;i++)
{
f[i] = 0;
}
h.clear();
add = 1;
}
void update(long long int p, long long int v)
{
if (p == 0)
{
return ;
}
if (add)
{
h.push_back({p, v});
}
while (p < 2 * maxn)
{
f[p] += v;
p += (p & -p);
}
return ;
}
long long int get(long long int p)
{
long long int ret = 0;
while (p > 0)
{
ret += f[p];
p -= (p & -p);
}
return ret;
}
long long int get(long long int l, long long int r)
{
if (r <= l)
{
return 0;
}
return get(r - 1) - get(l - 1);
}
void clear()
{
add = 0;
for (auto o : h)
{
update(o.first, -o.second);
}
h.clear();
add = 1;
return ;
}
};
Node fr, nocl, sr;
void init(long long int v)
{
vu[v] = 1;
mxhu[v] = htl[v];
for (auto u : ne[v])
{
htl[u] = htl[v] + 1;
init(u);
vu[v] += vu[u];
mxhu[v] = max(mxhu[v], mxhu[u]);
}
return ;
}
void upd(long long int v, long long int h)
{
nocl.update(htl[v] + 1, 1);
nocl.update(htl[v] + cycid[v], -1);
fr.update(h + hms, 1);
for (auto u : ne[v])
{
upd(u, h + 1);
}
return ;
}
void fdfs(long long int v)
{
if (ne[v].size() == 0)
{
hms = n;
fr.clear();
fr.update(hms, 1);
nocl.clear();
nocl.update(htl[v] + 1, 1);
nocl.update(htl[v] + cycid[v], -1);
}
else
{
pair <long long int, long long int> mx = {0, 0};
for (auto u : ne[v])
{
mx = max(mx, {vu[u], u});
}
for (auto u : ne[v])
{
if (u != mx.second)
{
fdfs(u);
}
}
fdfs(mx.second);
hms--;
for (auto u : ne[v])
{
if (u != mx.second)
{
upd(u, 1);
}
}
fr.update(hms, 1);
nocl.update(htl[v] + 1, 1);
nocl.update(htl[v] + cycid[v], -1);
}
long long int cn = k + dist[v] - id[v] + 1;
for (auto len : divs[cn - k + n])
{
if (isc[v])
{
ans[v] -= nocl.get(len);
}
if (len > mxhu[v])
{
continue;
}
long long int minb = max(0ll, len - 1 - dist[v] - (cl + lp - id[v]));
long long int maxb = len - 1 - dist[v];
ans[v] += fr.get(minb + hms, maxb + hms + 1);
//sdfsdfsdfsdf
//sdfsdfjlsjflsdkfj
}
if (cycid[v] != 1 and !isc[v])
{
cn = k - lp + dis[v] + (cl + 1 - cycid[v]);
for (auto len : divs[cn - k + n])
{
long long int minb = max(0ll, len - 1 - dis[v] - (cl - 1));
long long int maxb = len - 1 - dis[v] - (cl + 1 - cycid[v]);
if (minb > mxhu[v])
{
break;
}
ans[v] += fr.get(minb + hms, maxb + hms + 1);
}
}
//yal be jolo ke agabesh bashe
if (isc[v] and cycid[v] != 1)
{
cn = k - lp + dis[v] + (cl + 1 - cycid[v]);
for (auto len : divs[cn - k + n])
{
if (len < htl[v] + 1)
{
continue;
}
if (len > mxhu[v] + cl)
{
break;
}
ans[v] += nocl.get(len);
}
}
return ;
}
void filli(long long int v)
{
vu[v] = 1;
mark1[v] = 1;
for (auto u : ne[v])
{
if (mark1[u])
{
continue;
}
if (cycid[u] == 0)
{
cycid[u] = cycid[v];
}
if (dist[u] == -1)
{
dist[u] = dist[v] + 1;
}
filli(u);
vu[v] += vu[u];
}
return ;
}
pair <long long int, long long int> f(long long int v)
{
long long int nom = 0;
long long int cur = v;
while (mark1[cur] == 0)
{
mark1[cur] = 1;
cur = nxt[cur];
}
long long int ret = cur;
do
{
nom++;
cur = nxt[cur];
}while (cur != ret);
while (mark1[v])
{
dist[v] = 0;
mark1[v] = 0;
v = nxt[v];
}
return {ret, nom};
}
void upd2(long long int v)
{
sr.update(htl[v], 1);
for (auto u : ne[v])
{
upd2(u);
}
return ;
}
void ldfs(long long int v)
{
markl[v] = 1;
if (nxt[v] != csv)
{
ldfs(nxt[v]);
}
long long int cn = k + dist[v] - id[v] + 1;
for (auto len : divs[cn - k + n])
{
ans[v] += nocl.get(len);
ans[v] -= sr.get(len - 1) - sr.get(len - cycid[v]);
}
for (auto u : ne[v])
{
if (markl[u])
{
continue;
}
upd2(u);
}
sr.update(htl[v], 1);
}
int main()
//void solve()
{
// ifstream cin("in.in");
// ofstream cout("out.out");
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n >> k;
for (long long int i = 1;i <= n;i++)
{
dist[i] = -1;
}
for (long long int i = 1;i <= n;i++)
{
long long int tmp = (k - n + i - 1) / i;
for (long long int j = tmp * i;j <= k + n;j += i)
{
divs[j - k + n].push_back(i);
}
}
for (long long int i = 1;i <= n;i++)
{
cin >> nxt[i];
ne[nxt[i]].push_back(i);
}
pair <long long int, long long int> tmp = f(1);
long long int v = tmp.first, l = tmp.second;
csv = v;
cl = l;
lp = 0;
long long int cur = 1;
while (cur != v)
{
cur = nxt[cur];
lp++;
l++;
}
long long int temp = k - lp;
cur = v;
while (temp % (l - lp))
{
temp--;
cur = nxt[cur];
}
long long int sv = cur;
tmp = f(1);
v = tmp.first, l = tmp.second;
cur = v;
long long int ccycid = 1;
while (nxt[cur] != v)
{
cycid[cur] = ccycid++;
isc[cur] = 1;
cur = nxt[cur];
}
isc[cur] = 1;
cycid[cur] = ccycid;
filli(cur);
for (long long int i = 1;i <= n;i++)
{
if (mark1[i])
{
continue;
}
tmp = f(i);
v = tmp.first;
long long int ll = tmp.second;
cur = v;
long long int cid = 1;
vector <long long int> c = {0}, dp = {0};
do
{
ans[sv] += n;
mark1[cur] = 1;
bfs.push(cur);
c.push_back(cur);
dp.push_back(0);
ans[cur] += l + lp;
id[cur] = cid++;
cur = nxt[cur];
}while (cur != v);
dp.push_back(0);
while (bfs.size())
{
long long int v = bfs.front();
bfs.pop();
for (auto u : ne[v])
{
if (mark1[u])
{
continue;
}
mark1[u] = 1;
dis[u] = dis[v] + 1;
id[u] = id[v];
bfs.push(u);
dp[0] += ((l + lp) - 1) / ll;
long long int st = id[u] + ((k - l - lp - dis[u]) % ll);
st %= ll;
if (st == 0)
{
st = ll;
}
long long int fn = st + l + lp - 1;
fn %= ll;
if (fn == 0)
{
fn = ll;
}
dp[st]++;
dp[fn + 1]--;
if (fn + 1 <= st)
{
dp[0]++;
}
ans[sv] += n;
}
}
long long int pl = 0;
for (long long int i = 0;i <= ll;i++)
{
pl += dp[i];
ans[c[i]] += pl;
}
}
for (long long int i = 1;i <= n;i++)
{
mark1[i] = 0;
}
cur = 1;
long long int cid = 1;
vector <long long int> c = {0}, dp = {0};
do
{
if (cid > lp)
{
ans[cur] += lp;
mark1[cur] = 1;
bfs.push(cur);
c.push_back(cur);
dp.push_back(0);
}
id[cur] = cid++;
cur = nxt[cur];
}while (cid <= l + lp);
dp.push_back(0);
while (bfs.size())
{
long long int v = bfs.front();
bfs.pop();
for (auto u : ne[v])
{
if (mark1[u])
{
continue;
}
mark1[u] = 1;
dis[u] = dis[v] + 1;
bfs.push(u);
if (id[u] == 0)
{
id[u] = id[v];
ans[sv] += n;
}
if (id[u] == 1)
{
continue;
}
dp[0] += (min(id[u] - 1, lp) - 1) / l;
long long int st;
if (id[u] > lp)
{
st = id[u] - lp + (k - lp - dis[u]) % l;
}
else
{
st = 1 + (k - (id[u] - 1) - dis[u]) % l;
}
st %= l;
if (st == 0)
{
st = l;
}
long long int fn;
long long int hmf;
if (id[u] <= lp)
{
fn = st + id[u] - 1 - 1;
hmf = id[u] - 1 - 1;
}
else
{
fn = st + lp - 1;
hmf = lp - 1;
}
fn %= l;
if (fn == 0)
{
fn = l;
}
dp[st]++;
dp[fn + 1]--;
if (fn + 1 <= st)
{
dp[0]++;
}
}
}
long long int pl = 0;
for (long long int i = 0;i <= l;i++)
{
if (lp)
pl += dp[i];
ans[c[i]] += pl;
}
cur = csv;
while (nxt[cur] != csv)
{
cur = nxt[cur];
}
for (auto it = ne[csv].begin();it != ne[csv].end();it++)
{
if ((*it) == cur)
{
ne[csv].erase(it);
break;
}
}
fr.init();
nocl.init();
sr.init();
htl[cur] = 1;
init(cur);
fdfs(cur);
ldfs(csv);
for (long long int i = 1;i <= n;i++)
{
cout << ans[i] << '\n';
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |