「BJOI2017」树的难题 TJ+卡题
题目大意
- 给定一棵 \(n\) 个点的树，每条边有颜色，第 \(i\) 种颜色权值为 \(v_i\)，共 \(m\) 种颜色。
- 对于树上一条路径，其权值定义为：经过边的颜色依次组成序列，每个相同颜色段的颜色权值之和。
- 如：颜色序列 \(1,2,2,1,1,4\)，其权值为 \(v_1+v_2+v_1+v_4\)。
- 给定一对 \(l\)，\(r\)，求出长度在 \([l,r]\) 内的路径的最大权值。
- \(1 \le n,m \le 2 \times 10^5,1\le l,r \le n,\mid v_i \mid \le10^4\)。
分析
这道题想清楚了很简单。
首先看到这个路径问题，就往点分治上靠，不是点分树，被骗了吧，哈哈哈。
重心下单条链是很好算权值的，关键点在于两条链拼接起来，顶端的贡献问题。
想一想可以发现，其实对于每条链，其他的链顶端只有相同和不相同两种。
那就可以一种颜色一种颜色的处理，就可以很方便地维护相同和不相同的颜色。
所以第一步把儿子都提出来，然后按边的颜色排序。
将相同颜色的贡献用 \(now\) 存储，不同的用 \(lst\) 存储。
依次扫描每个儿子，进行如下操作：
- 遍历其子树，存下每条链的长度和权值。
- 查询 \(now\) 和 \(lst\) 中答案。
- 如果和上个儿子的顶端一样，并入 \(now\)；否则将 \(now\) 并入 \(lst\)，然后清空 \(now\) 再并入。
现在就是查询的问题了。
如果这条链长度是 \(len\)，那么另一半长度就要求在 \([l-len,r-len]\) 内。
显然是一个区间查询问题，因为最值不能容斥，硬上线段树。
然后简单做就行了。
实现细节
首先是一个很关键的答案组成问题。
我们查询线段树的时候，如果长度不是从 \(0\) 开始，就需要将一条链组成答案的情况特判。
这个表现在样例一，但测试数据内没有 hack 这个问题……
写了三天的 lq 不过样例，一怒之下提交 AC。
然后就是线段树区间查询问题，记得跟上下界取 \(\min\) 和 \(\max\)。
线段树涉及到多次清空的问题，动态开点的话可以在新建节点时操作，固定结构的话就用一个 \(lazy-tag\)，访问的时候下传标记即可。
还有两棵权值线段树的合并，这个题里面可以直接用 std::vector 存进行过的操作，然后重新插入一次，毕竟多码多错，少码少错，不码不错。
Code：
经典的放一半，就问你气不气：
实在需要拿去对拍啥的也可以找我，虽然我也想不出怎么找我。
SegmentTree lst,now;//lst 和 now 的作用见上
std::vector<std::pair<int,long long>> vec;
std::vector<std::pair<int,long long>> pos;
//vec 是当前子树，pos 是当前所有同色的子树
std::vector<edge> son;//存儿子
void work_calc(int u,int fa,int col,int dep,long long dis){
vec.emplace_back(dep,dis);//递归计算深度与权值
for(edge e:G[u])
if(!vis[e.ver]&&e.ver!=fa)
work_calc(e.ver,u,e.col,dep+1,dis+(e.col==col?0:val[e.col]));
}
void solve(int u){
vis[u]=1;
son.clear();
for(edge e:G[u])
if(!vis[e.ver])
son.emplace_back(e);
std::sort(son.begin(),son.end(),[](edge x,edge y)->bool{
return x.col<y.col;
});//排序
//lambda 表达式，https://oi-wiki.org/lang/lambda/ 有介绍
int lst_col={-1};//上一个颜色
lst.init(all);//链的长度不会超过根的 size
now.init(all);
pos.clear();
for(auto e:son){
if(~lst_col){
vec.clear();
work_calc(e.ver,u,e.col,1,val[e.col]);//计算链
if(e.col==lst_col){//颜色相同
for(auto it:vec)
ans=std::max({ans,l<=it.first&&it.first<=r?it.second:-Inf,lst.query(l-it.first,r-it.first)+it.second,now.query(l-it.first,r-it.first)+it.second-val[e.col]});//查询
for(auto it:vec)
now.updata(it.first,it.second),pos.emplace_back(it.first,it.second);//更新
}
else{//新颜色
for(auto it:pos)
lst.updata(it.first,it.second);//此时之前的 now 等效于 lst
pos.clear();
now.init(all);
for(auto it:vec)
ans=std::max({ans,l<=it.first&&it.first<=r?it.second:-Inf,lst.query(l-it.first,r-it.first)+it.second});
for(auto it:vec)//清空后的新数据
now.updata(it.first,it.second),pos.emplace_back(it);
}
lst_col=e.col;
}
else{//特殊处理第一棵
vec.clear();
work_calc(e.ver,u,e.col,1,val[e.col]);
for(auto it:vec)
ans=std::max(ans,l<=it.first&&it.first<=r?it.second:-Inf);
for(auto it:vec)
now.updata(it.first,it.second),pos.emplace_back(it);
lst_col=e.col;
}
}
//...递归继续处理
}