题解 SP375 【QTREE - Query on a tree】

\[\texttt{Preface}
\]

这题在 \(\text{Luogu}\) 上竟然不能交 \(C++\) ，会一直 \(Waiting\) ，只能交非 \(C++\) 的语言。

所以打完了 \(C++\) 要转到 \(C\) 才能过。

要把什么 \(swap\) ， \(max\) 各种函数换成手写，以及 \(C++\) 的特色（例如 using namespace std; 和 inline ）都要去掉。

详情见 \(Code\) 。

\[\texttt{Description}
\]

给出一个 \(n\) 个点的带权树，需要支持以下操作：

CHANGE i ti 将第 \(i\) 条边的权值改为 \(t_i\) 。
QUERY a b 询问 \(a\) 到 \(b\) 的路径上最大边权。

多组数据。

\[\texttt{Solution}
\]

从这个询问 " 查询路径信息，边带修 " 来说，我们可以知道这是一个树剖板子题。

不了解树剖的童鞋可以去了解一下，过一下树剖模板。

只不过这题不是一般的 " 点带修 " 而是 " 边带修 " ，也不要紧。

注意到除了根，每个节点都有父亲，那么我们可以把边的信息转化到点身上，每个节点的点权是它与它父亲所形成的边的边权。

例如 \(1\) 到 \(2\) 的一条长度为 \(3\) 的边（此时 \(1\) 是 \(2\) 的父亲），那么我们可以理解为 \(2\) 的点权是 \(3\) 。

这样就可以用树剖维护了。

但是令 \(z=\text{lca}(x,y)\) ，我们发现 \((fa[z],z)\) 这条边是不能被算进答案的。

在查询的最后一步，\(x\) 和 \(y\) 会在同一条重链上（设 \(dep_x<dep_y\)），此时 \(x\) 就是 \(z\) ，由于重链上的节点的 \(dfs\) 序是连续的，所以查询 \([dfn_x+1,dfn_y]\) 这段区间的最大值就可以避开计算 \(z\) 的信息了。

\[\texttt{Code}
\]

#include<stdio.h>

#define N 10100

#define M 20100

int read()

{

	int x=0,f=1;char s=getchar();

	while(s<'0'||s>'9'){if(s=='-')f=-f;s=getchar();}

	while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();}

	return x*f;

}

int tmp;

int max(int a,int b){return a>b?a:b;} 

int T;

int n;

struct Edge{

	int u,v,w;

}e[N];

int tot,head[N],ver[M],edge[M],Next[M];

void add(int u,int v,int w)

{

	ver[++tot]=v;    edge[tot]=w;    Next[tot]=head[u];    head[u]=tot;

}

int val[N];

int d[N];

int fu[N];

int size[N];

int son[N];

void dfs1(int u)

{

	size[u]=1;

	for(int i=head[u];i;i=Next[i])

	{

		int v=ver[i],w=edge[i];

		if(v==fu[u])continue;

		fu[v]=u;

		val[v]=w;

		d[v]=d[u]+1;

		dfs1(v);

		size[u]+=size[v];

		if(size[son[u]]<size[v])son[u]=v;

	}

}

int QwQ;

int dfn[N],idx[N];

int top[N];

void dfs2(int u)

{

	QwQ++;

	dfn[u]=QwQ,idx[QwQ]=u;

	if(son[u])

	{

		top[son[u]]=top[u];

		dfs2(son[u]);

	}

	for(int i=head[u];i;i=Next[i])

	{

		int v=ver[i];

		if(v==fu[u]||v==son[u])continue;

		top[v]=v;

		dfs2(v);

	}

}

struct SegmentTree{

	int l,r;

	int max;

}t[N*4];

void upd(int p)

{

	t[p].max=max(t[p*2].max,t[p*2+1].max);

}

void build(int p,int l,int r)

{

	t[p].l=l,t[p].r=r;

	if(l==r)

	{

		t[p].max=val[idx[l]];

		return;

	}

	int mid=(l+r)/2;

	build(p*2,l,mid);

	build(p*2+1,mid+1,r);

	upd(p);

}

void change(int p,int delta,int val)

{

	if(t[p].l==t[p].r)

	{

		t[p].max=val;

		return;

	}

	int mid=(t[p].l+t[p].r)/2;

	if(delta<=mid)

		change(p*2,delta,val);

	else

		change(p*2+1,delta,val);

	upd(p);

}

int ask(int p,int l,int r)

{

	if(l<=t[p].l&&t[p].r<=r)return t[p].max;

	int mid=(t[p].l+t[p].r)/2;

	int val=0;

	if(l<=mid)

		val=max(val,ask(p*2,l,r));

	if(mid<r)

		val=max(val,ask(p*2+1,l,r));

	return val;

}

int path_ask(int u,int v)

{

	int ans=0;

	while(top[u]!=top[v])

	{

		if(d[top[u]]>d[top[v]])tmp=u,u=v,v=tmp;

		ans=max(ans,ask(1,dfn[top[v]],dfn[v]));

		v=fu[top[v]];

	}

	if(u==v)return ans;

	if(d[u]>d[v])tmp=u,u=v,v=tmp;

	ans=max(ans,ask(1,dfn[u]+1,dfn[v]));

	return ans;

}

void work()

{

	tot=QwQ=0;

	for(int i=1;i<=n;i++)

		head[i]=son[i]=0;

	n=read();

	for(int i=1;i<n;i++)

	{

		e[i].u=read(),e[i].v=read(),e[i].w=read();

		add(e[i].u,e[i].v,e[i].w),add(e[i].v,e[i].u,e[i].w);

	}

	d[1]=1,top[1]=1;

	dfs1(1),dfs2(1);

	build(1,1,n);

	char opt[10];

	while(scanf("%s",opt),opt[0]!='D')

	{

		int x=read(),y=read();

		switch(opt[0])

		{

			case 'C':{

				if(d[e[x].u]>d[e[x].v])

					tmp=e[x].u,e[x].u=e[x].v,e[x].v=tmp;

				change(1,dfn[e[x].v],y);

				break;

			}

			case 'Q':{

				printf("%d\n",path_ask(x,y));

				break;

			}

		}

	}

}

int main()

{

	T=read();

	while(T--)     work();

	return 0;

}

\[\texttt{Thanks} \ \texttt{for} \ \texttt{watching}
\]

巴特西

题解 SP375 【QTREE - Query on a tree】

最新文章

热门文章