题意小 X 有一颗nnn个结点的树树的根结点为111规定根结点的深度为111。树是指一个由nnn个结点n−1n-1n−1条双向边组成的连通块。你通过每条边都需要111秒。你在每秒钟可以停在原地也可以经过111条边。树的结点会随机刷新mmm次第iii次在tit_iti​时刻在wiw_iwi​号结点刷新出pip_ipi​个苹果但存在时间只有111过后会消失。这颗树有两个特殊的性质最深的结点深度不会超过sss。所有的tit_iti​均不相同。最开始时你在根结点请问你最多能采多少个苹果。1≤n≤8×104,1≤m≤2×104,1≤s≤103,1≤pi,ti≤109,1≤wi≤n1 \le n \le 8 \times 10^4,1 \le m \le 2 \times 10^4,1 \le s \le 10^3,1 \le p_i,t_i \le 10^9,1 \le w_i \le n1≤n≤8×104,1≤m≤2×104,1≤s≤103,1≤pi​,ti​≤109,1≤wi​≤n。思路复健回来第一道绿题不过感觉以我上一年的思维能力也要卡很久……在点与点之间移动需要用 lca 求距离。这个有时间的完全搞不了贪心所以考虑 dp。将所有条件按时间排序设fi,0/1f_{i,0/1}fi,0/1​表示第iii个条件取或不取发现0/10/10/1没啥用直接设fif_ifi​表示必取第iii个条件的苹果时的最大答案不难写出转移fimax⁡tjti,ti−tj≥dis(wi,wj){fjpi}f_i\max_{t_jt_i,t_i-t_j\ge \text{dis}(w_i,w_j)} \{f_jp_i\}fi​tj​ti​,ti​−tj​≥dis(wi​,wj​)max​{fj​pi​}因为要求距离所以转移是O(m2log⁡s)O(m^2\log s)O(m2logs)的。for(inti1;im;i){if(Dis(1,a[i].u)t[i])f[i]a[i].p;//初始状态直接从根节点过来能不能到for(intj1;ji;j){if(t[j]t[i])break;if(t[i]-t[j]Dis(a[i].u,a[j].u))f[i]max(f[i],f[j]a[i].p);}}发现那个log⁡\loglog优化不了考虑剪枝减少可转移的jjj的数量。题目中还有个条件没用上树的最大深度为sss。一开始我也疑惑很久给个最大深度有什么用后来发现sss比mmm小一个数量级。同学教了我一个很重要的结论在树上两点间最大距离≤2s\le 2s≤2s。那么ti−tj≥2st_i-t_j\ge 2sti​−tj​≥2s的最大的j′jj′其之前的fjf_jfj​都可以合法转移到fif_ifi​。这是因为tj≤tj′t_j\le t_{j}tj​≤tj′​ti−tj≥2st_i-t_j\ge 2sti​−tj​≥2s便恒成立。于是考虑维护 dp 数组的前缀最大值iii向前遍历到j′jj′时直接用前缀最大值转移j′∼ij\sim ij′∼i照常转移即可。时间复杂度刚好压到O(mslog⁡s)O(ms\log s)O(mslogs)。被剪枝的魅力深深震撼到了。代码#includebits/stdc.husingnamespacestd;#definelllonglongconstll N8e49,M2e49;ll n,m,mx;ll idx,head[N];structedge{ll to,next;}e[N1];voidaddedge(ll u,ll v){idx;e[idx].tov;e[idx].nexthead[u];head[u]idx;}ll dep[N],fat[N],siz[N];ll big[N],top[N];voiddfs(ll u,ll fa){dep[u]dep[fa]1;fat[u]fa;siz[u]1;for(intihead[u];i;ie[i].next){ll ve[i].to;if(vfa)continue;dfs(v,u);siz[u]siz[v];if(!big[u]||siz[big[u]]siz[v])big[u]v;}}voiddfs2(ll u,ll fa,ll tp){top[u]tp;if(big[u])dfs2(big[u],u,tp);for(intihead[u];i;ie[i].next){ll ve[i].to;if(vfa||vbig[u])continue;dfs2(v,u,v);}}lllca(ll x,ll y){while(top[x]!top[y]){if(dep[top[x]]dep[top[y]])xfat[top[x]];elseyfat[top[y]];}returndep[x]dep[y]?y:x;}llDis(ll x,ll y){returndep[x]dep[y]-2*dep[lca(x,y)];}structnode{ll t,u,p;}a[M];boolcmp(node x,node y){returnx.ty.t;}ll f[M],t[M],ma[M];intmain(){scanf(%lld%lld%lld,n,m,mx);//mx即题目中的sfor(inti1;in;i){ll u,v;scanf(%lld%lld,u,v);addedge(u,v);addedge(v,u);}dep[1]1;dfs(1,0);dfs2(1,0,1);for(inti1;im;i){ll t,u,p;scanf(%lld%lld%lld,u,t,p);a[i](node){t,u,p};}sort(a1,am1,cmp);for(inti1;im;i)t[i]a[i].t;ll ret0;for(inti1;im;i){if(Dis(1,a[i].u)t[i])f[i]a[i].p;//直接从根节点过来能不能到for(intji;j1;j--){if(t[i]t[j])continue;if(t[i]-t[j]2*mx)//2mx肯定能过来{f[i]max(f[i],ma[j]a[i].p);break;}if(t[i]-t[j]Dis(a[i].u,a[j].u))f[i]max(f[i],f[j]a[i].p);}ma[i]max(ma[i-1],f[i]);}printf(%lld,ma[m]);return0;}