树上倍增

https://codeforces.com/contest/702/problem/E

题意：

给一个n个点，n条有向边，n个权值的图，每个点一条出边
问所有的点按着有向边走k的权值和，还有k条边上的最小权值是多少，并输出

思路：

经典的倍增题目
先利用倍增找出子$2^p$的子节点是哪个，记为$ne[i][p]$
然后就可以记$sum[i][p]，minn[i][p]$为子$2^p$步的权值和，和最小权值
最后就是对$k$二进制从低位到高位分解
具体倍增就是$ne[i][p] = ne[ne[i][p-1]][p-1]$（从低往高递推），其他两个同理

#include<bits/stdc++.h>
#define debug1(a) cout<<#a<<'='<< a << endl;
#define debug2(a,b) cout<<#a<<" = "<<a<<"  "<<#b<<" = "<<b<<endl;
#define debug3(a,b,c) cout<<#a<<" = "<<a<<"  "<<#b<<" = "<<b<<"  "<<#c<<" = "<<c<<endl;
#define debug4(a,b,c,d) cout<<#a<<" = "<<a<<"  "<<#b<<" = "<<b<<"  "<<#c<<" = "<<c<<"  "<<#d<<" = "<<d<<endl;
#define debug5(a,b,c,d,e) cout<<#a<<" = "<<a<<"  "<<#b<<" = "<<b<<"  "<<#c<<" = "<<c<<"  "<<#d<<" = "<<d<<"  "<<#e<<" = "<<e<<endl;
#define endl "\n"
#define fi first
#define se second

#define int long long
using namespace std;

typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int,int> PII;
typedef pair<LL,LL> PLL;

//#pragma GCC optimize(3,"Ofast","inline")
//#pragma GCC optimize(2)
const int N = 1e5+10,P = 35;

int edge[N],w[N];
int ne[N][P];
int minn[N][P],sum[N][P];

void solve() 
{
    int n,k;cin >> n >> k;

    for(int i = 0;i < n;i ++)
        cin >> edge[i];
    for(int i = 0;i < n;i ++)
        cin >> w[i];
    
    for(int p = 0;p < P;p ++)
    {
        for(int i = 0;i < n;i ++)
        {
            if(p) ne[i][p] = ne[ne[i][p-1]][p-1];
            else ne[i][p] = edge[i];
        }
    }

    for(int p = 0;p < P;p ++)
    {
        for(int i = 0;i < n;i ++)
        {
            if(p) 
            {
                sum[i][p] = sum[i][p-1] + sum[ne[i][p-1]][p-1];
                minn[i][p] = min(minn[i][p-1],minn[ne[i][p-1]][p-1]);
            }
            else sum[i][p] = minn[i][p] = w[i];
        }
    }

    for(int i = 0;i < n;i ++)
    {
        int res_sum = 0,res_minn = 1e9;
        for(int start = i,j = 0;j < P;j ++)if(k >> j & 1)
        {
            res_sum += sum[start][j];
            res_minn = min(res_minn,minn[start][j]);
            start = ne[start][j];
        }
        cout << res_sum << " " << res_minn << endl;
    }
}

signed main()
{
    /*
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    */
    int T = 1;//cin >> T;

    while(T--){
        //puts(solve()?"YES":"NO");
        solve();
    }
    return 0;

}
/*

*/

原文链接: https://www.cnblogs.com/cfddfc/p/17063343.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍

原创文章受到原创版权保护。转载请注明出处：https://www.ccppcoding.com/archives/313364

非原创文章文中已经注明原地址，如有侵权，联系删除

关注公众号【高性能架构探索】，第一时间获取最新文章

转载文章受原作者版权保护。转载请注明原作者出处！

相关推荐