CF702E Analysis of Pathes in Functional Graph

倍增练习题。

基环树上倍增一下维护维护最小值和权值和，注意循环的时候$j$这维作为状态要放在外层循环，平时在树上做的时候一个一个结点处理并不会错，因为之前访问的结点已经全部处理过了。

时间复杂度$O(nlogk)$。

Code：

#include <cstdio>

#include <cstring>

using namespace std;

typedef long long ll;

const int N = 1e5 + ;

const int Lg = ;

const int inf = 0x3f3f3f3f;

int n, to[N][Lg];

ll stp, val[N], sum[N][Lg], minn[N][Lg];

template <typename T>

inline void read(T &X) {

    X = ; char ch = ; T op = ;

    for(; ch > ''|| ch < ''; ch = getchar())

        if(ch == '-') op = -;

    for(; ch >= '' && ch <= ''; ch = getchar())

        X = (X << ) + (X << ) + ch - ;

    X *= op;

}

template <typename T>

inline void chkMin(T &x, T y) {

    if(y < x) x = y;

}

template <typename T>

inline T min(T x, T y) {

    return x > y ? y : x;

}

inline void solve(int x) {

    ll resSum = 0LL, resMin = inf, tmp = stp;

    for(int i = ; i >= ; i--)

        if((tmp >> i) & ) {

            resSum += sum[x][i];

            chkMin(resMin, minn[x][i]);

            x = to[x][i];

        }

    printf("%lld %lld\n", resSum, resMin);

}

int main() {

    read(n), read(stp);

    for(int i = ; i <= n; i++) read(to[i][]), to[i][]++;

    for(int i = ; i <= n; i++) read(val[i]);

    memset(minn, 0x3f, sizeof(minn));

    for(int i = ; i <= n; i++)

        sum[i][] = minn[i][] = val[i];

    for(int j = ; j <= ; j++)

        for(int i = ; i <= n; i++)

         {

            to[i][j] = to[to[i][j - ]][j - ];

            minn[i][j] = min(minn[i][j - ], minn[to[i][j - ]][j - ]);

            sum[i][j] = sum[i][j - ] + sum[to[i][j - ]][j - ];

        }

/*    for(int i = 1; i <= n; i++)

        printf("%lld ", sum[i][1]);

    printf("\n");   */

    for(int i = ; i <= n; i++) solve(i);

    return ;

}