我写的是染色
求答案时合并信息是有顺序的,比较难处理
,为什么不能暴力判断拼接点是否有贡献
像以下这段代码
int G(int x , int y) {
int ans = 0;
while(top[x] != top[y]) {
if(dep[top[x]] < dep[top[y]]) swap(x , y);
ans += get(1 , 1 , n , dfn[top[x]] , dfn[x]).x;
// 下面这条语句就是处理拼接点的
ans += (get(1 , 1 , n , dfn[top[x]] , dfn[top[x]]).l == get(1 , 1 , n , dfn[f[top[x]]] , dfn[f[top[x]]]).l);
x = f[top[x]];
}
if(dep[x] > dep[y]) swap(x , y);
ans += get(1 , 1 , n , dfn[x] , dfn[y]).x;
return ans;
}
可是它只能获得20pt