马路树链剖分/线段树/最近公共祖先(LCA)

题目

【问题描述】

小迟生活的城市是⼀棵树（树指的是⼀个含有 (n) 个节点以及 (n-1) 条边的⽆向连通图），节点编号从 (1) 到 (n)，每条边拥有⼀个权值 (value)，表示通过这条边的时候你需要交纳的金钱（注意，有可能这个值为负数，也就是说你经过这条边的时候你可以赚钱）
小迟是⼀个杰出的马路工，他居住在节点 (s)，他能够选择任意⼀个节点 (m)，并将从节点 (s) 到节点 (m) 的简单路径（简单路径指的是不经过同⼀个节点两次）上的所有边的权值都修改为 (0).
现在小迟获得 (q) 个请求，每个请求都是以 (a) (b) 的形式给出，表示小迟的好朋友小早希望从节点 (a) 走简单路径到节点$ b$，小迟希望能最小化小早需要缴纳的钱。
需要注意的是，小迟获得的这 (q) 个请求是相互独立的，也就是说您只需要对于每⼀个请求，决定小迟的⼀个修路⽅案，使得小早需要缴纳的钱尽可能的少。

【输入格式】

输⼊⽂件名为 (road.in)。
第⼀行三个正整数为 (n,q,s)。
接下来 (n-1) 行，每行三个整数$ x$ (y) (z), 表示有⼀条边 ((x,y))，(value) 为$ z$。
接下来 (q) 行，每行两个正整数 (a) (b)，表示请求。

【输出格式】

输出⽂件名为 (road.out)。
(q) 行，每行⼀个整数，表示需要缴纳的最少的钱。

【样例输入】

【样例输出】

0
0

【样例解释】

对于第⼀次询问 (1) (2), ⼩迟可以修从 (1) 到 (2) 的路，从⽽使得⼩早不需要缴纳⾦钱；
对于第⼆次询问 (1) (3), ⼩迟可以修从 (1) 到 (3) 的路，从⽽使得⼩早不需要缴纳⾦钱。

【数据规模及约定】

对于 (30\%)的数据,(n≤1000,q≤1000).
对于 (100\%)的数据，(1≤n,q≤200000,1≤x,y≤n,|z|≤1000).

解法

首先考虑没有负权边的情况,显然只需要树链剖分维护,线段树维护区间和,回答询问时选取将两端点到(s)点的路径中,点权和较大的那一条修改为(0)权值即可.

然后考虑有负权边的情况.

我们可以以(s)为根节点建树,将每个点的权值设置为它到根节点的距离,记(x)为(u ightarrow v)简单路径中点权最大的点,显然将(s ightarrow x)路径中边设为(0)权值是最佳方案.要求这个最佳方案的缴纳钱数,需要用到(LCA).一个特殊情况是,如果(x)的权值为负,那么不删除为最佳方案.

综上,答案为

[weight[u]+weight[v]-2*weight[x]-max(f(u,v)-weight[x],0 ]

其中(f(u,v))表示(u ightarrow v)简单路径中点权最大的点的点权.

代码

#include<cstdio>
#include<algorithm>
using namespace std;
const int SIZE=500005;
const int INF=0x3F3F3F3F;

int n,q,s;
int weight[SIZE],weightx[SIZE],siz[SIZE],son[SIZE],dep[SIZE],Fa[SIZE],ID[SIZE],top[SIZE];

struct Tree
{
    int L,R;
    int sum,tag;
    #define L(v) T[v].L
    #define R(v) T[v].R
    #define sum(v) T[v].sum
    #define tag(v) T[v].tag
    #define LC(v) (v*2)
    #define RC(v) (v*2+1)
    #define pushup(v) sum(v)=max(sum(LC(v)),sum(RC(v)))
}T[SIZE*4];
void Build(int p,int L,int R)
{
    L(p)=L;R(p)=R;
    if(L==R){sum(p)=weightx[L];return;}
    int Mid=(L+R)>>1;
    Build(LC(p),L,Mid);
    Build(RC(p),Mid+1,R);
    pushup(p);
}

int query(int p,int L,int R)
{
    if(L>R(p)||R<L(p))return -INF;
    if(L<=L(p)&&R>=R(p))return sum(p);
    return max(query(LC(p),L,R),query(RC(p),L,R));
}

int head[SIZE],nex[SIZE],ver[SIZE],edge[SIZE],Tot=1;
void ins(int u,int v,int e){ nex[++Tot]=head[u]; head[u]=Tot; ver[Tot]=v; edge[Tot]=e; }

void DFS1(int u,int Dis)
{
	siz[u]=1;
	weight[u]=Dis;
	for(int i=head[u];i;i=nex[i])
	{
		int v=ver[i];
		if(dep[v])continue;
		dep[v]=dep[u]+1;
		Fa[v]=u;
		DFS1(v,Dis+edge[i]);
		siz[u]+=siz[v];
		if(siz[v]>siz[son[u]])son[u]=v;
	}	
}

int Cnt=0;
void DFS2(int u,int TOP)
{
	ID[u]=++Cnt;
	weightx[Cnt]=weight[u];
	top[u]=TOP;
	if(siz[u]==1)return;
	DFS2(son[u],TOP); 
	for(int i=head[u];i;i=nex[i])
	{
		int v=ver[i];
		if(v==Fa[u]||v==son[u])continue;
		DFS2(v,v);
	} 
}

int f(int u,int v)
{
	int Res=-INF;
	while(top[u]!=top[v])
	{
		if(dep[top[u]]<dep[top[v]])swap(u,v);
		Res=max(Res,query(1,ID[top[u]],ID[u]));
		u=Fa[top[u]];
	}
	if(dep[u]<dep[v])swap(u,v);
	Res=max(Res,query(1,ID[v],ID[u]));
	return Res; 
}

int LCA(int u,int v)
{
	while(top[u]!=top[v])
		dep[top[u]]<dep[top[v]]? v=Fa[top[v]] : u=Fa[top[u]];
	return dep[u]<dep[v]? u : v;
}

int main()
{
	freopen("road.in","r",stdin);
	freopen("road.out","w",stdout);
	scanf("%d%d%d",&n,&q,&s);
	int u,v,e;
	for(int i=1;i<n;i++)
	{
		scanf("%d%d%d",&u,&v,&e);
		ins(u,v,e);
		ins(v,u,e);
	}
	dep[s]=s;
	DFS1(s,0);
	DFS2(s,s);
	Build(1,1,n);
	while(q--)
	{
		scanf("%d%d",&u,&v);
		int x=LCA(u,v);
		printf("%d
",weight[u]+weight[v]-2*weight[x]-max(f(u,v)-weight[x],0));
	}
	return 0;
}

马路 树链剖分/线段树/最近公共祖先(LCA)

题目