栗子栗子

CodeForces 702E

Analysis of Pathes in Functional Graph

题目大意

大致是给你个有向图,每个顶点仅有一条出边,每条边有对应的权值,让你统计从每个顶点出发走K条边之后的权值和,以及途经的最小权值

数据范围

点数$ N \le 10^5 $,走的边数目$ K \le 10^{10} $,每条边的权值$ W \le 10^8 $
(T T一不小心没看见K很大结果WA了一发)

思路

倍增算法好神奇!只能说太神奇了!这题一开始思考的时候总觉得环是个非常麻烦的东西,但是突然发现倍增算法完全不用特殊考虑环!

这题看似是图论和数据结构,实际上放在树DP里面比较合适。

关于倍增算法,是一类算法的总称吧,我这里说的是应用于图论中的那种T T。
最常见的应用应该是最近公共祖先(LCA)问题了,不会的可以先去补一下LCA的若干种解法。

开了三个数组,son,sum,mi
son[i][j]表示结点i第$ 2^j $个儿子的编号
sum[i][j]表示结点i一直到第$ 2^j $个儿子路径上的边权和
mi[i][j]表示结点i一直到第$ 2^j $个儿子路径上的边权最小值
初始化son[i][0]=f[i]sum[i][0]=mi[i][0]=w[i]
然后进行转移和更新
son[i][j]=son[son[i][j-1]][j-1]
sum[i][j]=sum[i][j-1]+sum[son[i][j-1]][j-1]
mi[i][j]=min(mi[i][j-1],mi[son[i][j-1]][j-1])
预处理需要O($ nlogk $)的时间

接着对于每一个结点跑一下倍增,用tot一直累和,ans不断与mi数组对应值作比较更新最小值即可(需要预处理一下K的二进制问题,不过这是小case啦)

P.S. 我就是看不惯题目从$ 0 $~$ n-1 $编号,所以强行改成了$ 1 $~$ n $,大家不要介意哈

下面附上

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include <iostream>
#include <cstring>
#include <stack>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <queue>
#include <cstdio>
#include <cstdlib>
#include <climits>
#include <deque>
#include <bitset>
#include <algorithm>

using namespace std;

const double eps=1e-10;
const double pi=3.1415926535897932384626433832795;
const double eln=2.718281828459045235360287471352;

#define LL long long
#define IN freopen("in.txt", "r", stdin)
#define OUT freopen("out.txt", "w", stdout)
#define scan(x) scanf("%d", &x)
#define scan2(x, y) scanf("%d%d", &x, &y)
#define scan3(x, y, z) scanf("%d%d%d", &x, &y, &z)
#define sqr(x) (x) * (x)
#define pr(x) printf("Case %d: ",x)
#define prn(x) printf("Case %d:\n",x)
#define prr(x) printf("Case #%d: ",x)
#define prrn(x) printf("Case #%d:\n",x)
#define lowbit(x) (x&(-x))

const int maxn=100005;

int a[maxn][50],son[maxn][50];
LL sum[maxn][50],mi[maxn][50];
int w[50];
int q;
LL i,j,k,l,m,n;

int main()
{
scanf("%lld%lld",&n,&m);k=m;
q=0;while(m>0){w[++q]=m%2;m/=2;}w[q+1]=0;
memset(mi,0x3f3f3f3f,sizeof(mi));m=k;
for(i=1;i<=n;i++){int x;scanf("%d",&x);son[i][0]=x+1;}
for(i=1;i<=n;i++)
{
scanf("%lld",&k);
sum[i][0]=mi[i][0]=k;
}
for(j=1,k=2;k<=m;j++,k*=2)
for(i=1;i<=n;i++)
{
son[i][j]=son[son[i][j-1]][j-1];
sum[i][j]=sum[i][j-1]+sum[son[i][j-1]][j-1];
mi[i][j]=min(mi[i][j-1],mi[son[i][j-1]][j-1]);
}
for(i=1;i<=n;i++)
{
LL tot,ans;
tot=0;ans=0x3f3f3f3f;
int t,num;
num=q+1;t=i;
while(num>0)
{
while(w[num]==0 && num>0)num--;
if(num<=0)break;
tot+=sum[t][num-1];
ans=min(ans,mi[t][num-1]);
t=son[t][num-1];
num--;
}
printf("%lld %lld\n",tot,ans);
}
return 0;
}