【题目链接】
http://www.lydsy.com/JudgeOnline/problem.php?id=1095
【题意】
给定一棵树，树上颜色或白或黑而且可以更改，多个询问求最远黑点之间的距离。
【思路】
括号序列+线段树
对树进行一遍dfs我们可以得到一个括号序列。如：
[A[B[E][F[H][I]]][C][D[G]]]
E和G之间去掉匹配的括号和字母之后的串就是：
]][[
把它看作一个二元组(a,b)表示有a个]和b个[，而且这个二元组的形式一定是…]]]][[[…的，则E G之间的距离为a+b。
线段树维护：每个节点维护7个值如下
a,b:分别表示]和[的数量
dis:max{ a+b } S’为S子串
l1:max{ a+b } S’为S的后缀，且S’紧跟在一个黑色点之后
l2:max{ b-a } S’为S的后缀，且S’紧跟在一个黑色点之后
r1:max{ a+b } S’为S的前缀，且一个黑色点紧跟在S’之后
r2:max{ a-b } S’为S的前缀，且一个黑色点紧跟在S’之后
合并线段树的左右儿子L和R：
dis=max{ L.dis,R.dis,L.a+R.b+|L.b-R.a| }
=max{ L.dis,R.dis,max{ L.r1+R.l2,L.r2+R.l1 } }
//R’定义为R的前缀，且一个黑色点紧跟在R’之后
l1=max{ L.l1 , L.a+R’.b+|L.b-R’.a| }
=max{ L.l1 , max{ R.l2+L.a+L.b , R.l1+L.a-L.b } }
l2=max{ L.l2 , max{ R’.b+L.b-R’.a-L.a , R’.b-L.a-R’.a+L.b } }
=max{ L.l2 , R.l2+L.b-L.a }
r1与r2的[推倒]同理，此处略去，直接给出：
r1=max{ R.r1 , max{ L.r1,R.a+R.b , L.r2+R.a+R.b } }
r2=max{ R.r2 , L.r2+R.a-R.b }
【代码】
#include<set>
#include<map>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define FOR(a,b,c) for(int a=b;a<=c;a++)
#define trav(u,i) for(int i=front[u];i;i=e[i].nxt)
using namespace std; typedef long long ll;
const int N = 1e6+;
const int inf = <<; //不要太大 ll read() {
char c=getchar();
ll f=,x=;
while(!isdigit(c)) {
if(c=='-') f=-; c=getchar();
}
while(isdigit(c))
x=x*+c-'',c=getchar();
return x*f;
} int n,q,tot;
int vis[N],num[N],pos[N]; struct Edge { int v,nxt;
}e[N<<];
int en=,front[N];
void adde(int u,int v)
{
e[++en]=(Edge){v,front[u]}; front[u]=en;
} struct Tnode {
int a,b,dis,l1,l2,r1,r2;
void val(int x) {
a=b=;
dis=l1=l2=r1=r2=-inf;
if(x==-) b=;
else if(x==-) a=;
else if(vis[x]==) l1=l2=r1=r2=;
}
void merge(Tnode L,Tnode R) {
a=L.a+max(,R.a-L.b);
b=R.b+max(,L.b-R.a);
dis=max(max(L.dis,R.dis),max(L.r1+R.l2,L.r2+R.l1));
l1=max(L.l1,max(R.l1-L.b+L.a,R.l2+L.b+L.a));
l2=max(L.l2,R.l2+L.b-L.a);
r1=max(R.r1,max(L.r1-R.a+R.b,L.r2+R.a+R.b));
r2=max(R.r2,L.r2+R.a-R.b);
}
}T[N<<]; void build(int u,int l,int r)
{
if(l==r) T[u].val(num[l]);
else {
int mid=(l+r)>>;
build(u<<,l,mid);
build(u<<|,mid+,r);
T[u].merge(T[u<<],T[u<<|]);
}
}
void update(int u,int l,int r,int rk)
{
if(l==r) T[u].val(num[l]);
else {
int mid=(l+r)>>;
if(rk<=mid) update(u<<,l,mid,rk);
else update(u<<|,mid+,r,rk);
T[u].merge(T[u<<],T[u<<|]);
}
} void dfs(int u,int fa)
{
num[++tot]=-;
pos[num[++tot]=u]=tot;
trav(u,i) if(e[i].v!=fa)
dfs(e[i].v,u);
num[++tot]=-;
} int main()
{
n=read();
int cnt=n;
FOR(i,,n) vis[i]=;
FOR(i,,n-) {
int u=read(),v=read();
adde(u,v),adde(v,u);
}
dfs(,-);
build(,,tot);
q=read();
char op[]; int x;
while(q--) {
scanf("%s",op);
if(op[]=='G') {
if(cnt==) puts("-1");
else if(cnt==) puts("");
else printf("%d\n",T[].dis);
}
else {
x=read();
cnt+=vis[x]=-vis[x];
update(,,tot,pos[x]);
}
}
return ;
}
Cqx论文 click here