安徽平台网站建设公司,盐城市网站建设公司,网站技术报务费如何做会计分录,wordpress 文章 样式文章目录 [Omsk Metro (simple version)](https://codeforces.com/contest/1843/problem/F1)问题分析1.分析如何知道根节点到某个结点的区间内是否存在一个子段和为k2.方法1使用树形DP来动态维护每个节点到根节点的最大子段和和最小子段和代码 Omsk Metro (simple version) 问题… 文章目录 [Omsk Metro (simple version)](https://codeforces.com/contest/1843/problem/F1)问题分析1.分析如何知道根节点到某个结点的区间内是否存在一个子段和为k2.方法1使用树形DP来动态维护每个节点到根节点的最大子段和和最小子段和代码 Omsk Metro (simple version) 问题分析
给定一个树形结构的起始点然后有q次操作每次操作有两种一种为向该树形结构已存在的点中添加结点另一种为查询根节点到某个已存在结点中是否存在一个连续子段其和为k。每个结点的都有一个权值权值为-1或者1。
1.分析如何知道根节点到某个结点的区间内是否存在一个子段和为k
假设该区间内存在一个子段其和为k考虑该子段和相邻子段的关系若将该子段进行扩展由于每个结点权值为-1或者1则每次扩展一个结点后比扩展前的和要多1或者少1即值的增减是连续的。则对于整个区间而言存在一个子段和为k等价于k属于该区间内最大子段和到最小子段和的范围内。
2.方法1使用树形DP来动态维护每个节点到根节点的最大子段和和最小子段和
由于新增节点后其子段和的最值只涉及其父节点则可以采用树形DP来动态维护所需的值。对于一个节点其状态定义有两个一个为 f 1 ( v ) f1(v) f1(v)表示1到v区间中的最大子段和另一个位 f 2 ( v ) f2(v) f2(v)为表示1到v区间中的最小子段和。状态转移的方式有两类一类为包括v点一类为不包括v点 f ( v , 0 ) f(v,0) f(v,0)为不包括v点, f ( v , 1 ) f(v,1) f(v,1)为包括v点。
不包括v点的可以由包含父节点的子段不包含父节点的子段以及都不包含3种状态转移而来。 f ( v , 0 ) f(v,0) f(v,0){ f ( u , 0 ) , f ( u , 1 ) f(u,0),f(u,1) f(u,0),f(u,1),0}
包括v点的可以由包含父节点的子段加上当前点的值仅有当前点的值2种状态转移而来。 f ( v , 1 ) f(v,1) f(v,1){ f ( u , 1 ) v a l , v a l f(u,1)val,val f(u,1)val,val}
代码
#includebits/stdc.h#define x first
#define y second
using namespace std;
typedef unsigned long long ULL;
typedef long long LL;
typedef pairint, int PII;
typedef pairLL, LL PLL;
const int N 2e5 10, M N 6, INF0x3f3f3f3f;
int f1[N][2],f2[N][2];void solve() {int n;cin n;///由于每个结点只会在添加时通过其父节点更新故只需初始化根节点即可f1[1][1]1,f1[1][0]0;f2[1][1]1,f2[1][0]0;char op[2];int idx1;///节点编号for(int i0;in;i){scanf(%s,op);if(op[0]){int u,w;scanf(%d %d,u,w);idx;f1[idx][0]max({f1[u][0],f1[u][1],0});f1[idx][1]max({f1[u][1]w,w});f2[idx][0]min({f2[u][0],f2[u][1],0});f2[idx][1]min({f2[u][1]w,w});}else {int u,v,k;scanf(%d %d %d,u,v,k);int minvalmin(f2[v][0],f2[v][1]);int maxvalmax(f1[v][0],f1[v][1]);if(kminvalkmaxval) puts(YES);else puts(NO);}}
}int main() {int t 1;cin t;while (t--) solve();return 0;
}
