题目: http://codeforces.com/problemset/problem/1059/E
用倍增可以在 nlog 内求出每个节点占用一个 sequence 时最远可以向父节点延伸到的节点, 对每个节点作为 sequence 的最后一个元素向上延伸时, 将节点的父节点属性合并 (类似于并查集的操作),
存在优先队列里保证每次先操作 dep 最大的节点
- #include<iostream>
- #include<cstdio>
- #include<cmath>
- #include<queue>
- #include<vector>
- #include<string.h>
- #include<cstring>
- #include<algorithm>
- #include<set>
- #include<map>
- #include<fstream>
- #include<cstdlib>
- #include<ctime>
- #include<list>
- #include<climits>
- #include<bitset>
- #include<random>
- #include <ctime>
- #include <cassert>
- #include <complex>
- #include <cstring>
- #include <chrono>
- using namespace std;
- #define fio iOS::sync_with_stdio(false);cin.tie(0);cout.tie(0);
- #define fopen freopen("input.in", "r", stdin);freopen("output.in", "w", stdout);
- #define left asfdasdasdfasdfsdfasfsdfasfdas1
- #define set asfdasdasdfasdfsdfasfsdfasfdas2
- #define tan asfdasdasdfasdfasfdfasfsdfasfdas
- mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
- typedef long long ll;
- typedef unsigned int un;
- const int desll[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
- const int mod=1e9+7;
- const int maxn=1e5+1;
- const int maxm=1e5;
- const double eps=1e-8;
- const int csize=2;
- int n,k,m,ar[maxn];
- int f[maxn],tan[maxn][18],v[maxn],in[maxn],mark;
- ll ss[maxn][18];
- bool ma[maxn],que[maxn];
- priority_queue<pair<int,int>> qu;
- vector<int> ve[maxn];
- int dep[maxn];
- void dfs(int u,int pre)
- {
- if(pre>=0)dep[u]=dep[pre]+1;
- for(int i=0;i<ve[u].size();i++){
- int v=ve[u][i];
- if(v==pre)continue;
- dfs(v,u);
- }
- }
- int main()
- {
- int l;
- ll s,mx=0;f[1]=0;
- scanf("%d%d%I64d",&n,&l,&s);
- memset(in,0,sizeof(in));
- memset(tan,0,sizeof(tan));
- memset(ma,0,sizeof(ma));
- memset(que,0,sizeof(que));
- for(int i=1;i<=n;i++)scanf("%d",&ar[i]),mx=max(mx,1LL*ar[i]);
- for(int i=2;i<=n;i++)scanf("%d",&f[i]),in[f[i]]++,ve[f[i]].push_back(i);
- dep[1]=1;
- dfs(1,-1);
- if(mx>s){
- printf("-1\n");
- return 0;
- }
- for(int i=1;i<=n;i++){
- tan[i][0]=f[i];
- ss[i][0]=ar[f[i]];
- }
- for(int j=1;j<18;j++){// 倍增预处理
- for(int i=1;i<=n;i++){
- if(i + (1<<j)>n)break;
- tan[i][j]=tan[tan[i][j-1]][j-1];
- ss[i][j] = ss[i][j-1]+ss[tan[i][j-1]][j-1];
- }
- }
- for(int i=1;i<=n;i++){
- ll lmid=l-1,smid=s-ar[i];
- int ins=17,x=i;
- while(ins>=0){
- if(tan[x][ins]==0)ins--;
- else if((1<<ins)> lmid)ins--;
- else if(ss[x][ins]<=smid){
- smid-=ss[x][ins];
- lmid -= (1<<ins);
- x=tan[x][ins];
- }
- else ins--;
- }
- v[i]=x;//v[i] 代表 i 节点作为 sequence 尾节点时最远可以向上延伸到的节点
- }
- for(int i=1;i<=n;i++){
- if(v[i]==0)exit(0);
- }
- for(int i=1;i<=n;i++){
- if(in[i]==0){
- qu.push(make_pair(dep[i],i));
- que[i]=1;
- }
- }
- int ans=0;
- while(qu.size()){
- int u=qu.top().second;qu.pop();
- if(ma[u])continue;// 如果已经标记过, 代表有其他节点可以延伸到此节点, 跳过即可
- mark=v[u];
- int mid=f[u],pre=u;
- while(dep[mid]>dep[mark]){// 对 ma 数组进行标记, 合并 f 数组, 类似于并查集的操作
- ma[pre]=1;
- f[pre]=mark;
- pre=mid;
- mid=f[mid];
- }
- ma[pre]=1;
- ma[mark]=1;
- if(pre!=mark)f[pre]=mark;
- ans++;
- //cout<<mark<<""<<f[mark]<<" "<<ma[f[mark]]<<" "<<que[f[mark]]<<endl;
- if(f[mark]>0 && !ma[f[mark]] && !que[f[mark]]){
- qu.push(make_pair(dep[f[mark]],f[mark]));
- que[f[mark]]=1;
- }
- }
- printf("%d\n",ans);
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2796365.html