原题传送门
一道题意很复杂的题目, 为了表达一句话的意思, 用了四句话去描述, 纯粹为了误导
大致题意: 一棵树, 每个结点 i 会有一个权值 weighti, 初始时只有一个权值为 0 的根节点 1 给定 Q(Q4*105)个操作, 操作分两类:
1.1 p q, 表示新建结点 cnt+1, 权值为 q, 该结点与 p 结点连边
2.2 p q, 表示求最长的序列 P, 满足 P1=p, 对 i>1, 都有: Pi 是 Pi-1 与根结点路径上离 Pi-1 最近的权值不小于 weighti 的点, 且所有 weightPi 加起来(有点拗口, 看不懂的可以看原题描述)
具体有一些区别: 其实就是强制在线辣, 请以实际描述为准
分析: 很明显能看出一些不变的东西: 结点只增不减, 而后续结点的加入不会影响之前结点的性质, 也就是说, 一个结点的信息在他加入的时候就已经完全确定, 而这些信息都能由祖先的信息推出, 于是想到倍增具体维护两个信息 st_par 和 st_sum(我代码里省事把 st_par 简写为 st,st_sum 简写为 sum), 其中 st_par[i][j]表示从结点 i 向上跳 2j 步的结点编号, 这里跳一步指的是进行一次寻找到根结点路径上第一个不小于当前结点权值的结点的操作, st_sum[i][j]表示跳的过程中所有经过结点 (不包括起点) 的权值之和能这样维护的原因是: 操作 2 中的序列其实是唯一的, 我只要能快速维护找到下一个结点的操作就行这样倍增的轮廓就出来了, 但是还有一件事要解决: 第一步也就是 st[i][0]怎么计算? 这里就要用到二分的思想了: 设 tmp 为 i 的父亲, 利用二分锁定离 i 最近的符合要求的点, 具体怎么实现就不用多说了, 我想说的是我原本的写法: 我原来写的是由 i 的父亲一步一步按 st[tmp][0]的方式往上跳, 实测两种写法没有任何时间上的差别, 但是复杂度肯定是不一样的
代码随便看看
- /* Codeforces 932D Tree
- 1st Edition:2018.2.15 Thursday
- 2nd Edition:2018.2.16 Friday
- Algorithm: 倍增
- */
- #include <iostream>
- #include <cstdio>
- #include <algorithm>
- #include <cmath>
- #include <cstring>
- #include <vector>
- #include <map>
- #include <set>
- #include <bitset>
- #include <queue>
- #include <deque>
- #include <stack>
- #include <iomanip>
- #include <cstdlib>
- #include <ctime>
- #include <cctype>
- using namespace std;
- #define is_lower(c) (c>=a && c<=z)
- #define is_upper(c) (c>=A && c<=Z)
- #define is_alpha(c) (is_lower(c) || is_upper(c))
- #define is_digit(c) (c>=0 && c<=9)
- #define stop system("PAUSE")
- #define ForG(a,b,c) for(rg int (a)=c.head[b];(a);(a)=c.E[a].nxt)
- #define For(a,b,c) for(rg int (a)=(b);(a)<=(c);++a)
- #define min(a,b) ((a)<(b)?(a):(b))
- #define max(a,b) ((a)>(b)?(a):(b))
- #define shl(x,y) ((x)<<(y))
- #define shr(x,y) ((x)>>(y))
- #define mp make_pair
- #define pb push_back
- #define rg register
- #ifdef ONLINE_JUDGE
- #define hash rename_hash
- #define next rename_next
- #define prev rename_prev
- #endif
- typedef long long ll;
- typedef unsigned long long ull;
- typedef pair<int,int> pii;
- typedef pair<ll,ll> pll;
- typedef vector<int> vi;
- typedef double db;
- const ll inf=1000000007LL;
- const db EPS=1e-14;
- const ll inf_ll=(ll)1e18;
- const ll maxn=400005LL;
- const ll mod=1000000007LL;
- int n,cnt;
- ll last;
- ll weight[maxn],sum[maxn][20];
- int par[maxn],st[maxn][20];
- int main(){
- scanf("%d",&n);
- cnt=1;
- while(n--){
- ll opt,p,q;
- scanf("%I64d %I64d %I64d",&opt,&p,&q);
- p^=last;q^=last;
- if(opt^2){
- par[++cnt]=p;
- weight[cnt]=q;
- int tmp=p;
- if(weight[tmp]<q){
- for(int i=19;i+1;--i) if(st[tmp][i] && weight[st[tmp][i]]<q){
- tmp=st[tmp][i];
- }
- tmp=st[tmp][0];
- }
- st[cnt][0]=tmp;
- sum[cnt][0]=weight[tmp];
- For(i,1,19) if(st[cnt][i-1] && st[st[cnt][i-1]][i-1]){
- st[cnt][i]=st[st[cnt][i-1]][i-1];
- sum[cnt][i]=sum[cnt][i-1]+sum[st[cnt][i-1]][i-1];
- }
- }else{
- ll nowsum=weight[p];
- if(nowsum>q){
- puts("0");
- last=0;
- continue;
- }
- int now=p,res=1;
- for(int i=19;i>=0;--i) if(st[now][i] && sum[now][i]+nowsum<=q){
- nowsum+=sum[now][i];
- now=st[now][i];
- res+=shl(1,i);
- }
- printf("%d\n",res);
- last=(ll)res;
- }
- }
- return 0;
- }
- View Code
来源: http://www.bubuko.com/infodetail-2499356.html