GDOI模拟数树数如何改写成长尾？

本文共计828个文字，预计阅读时间需要4分钟。

Description: 给定一棵N个节点的树，节点编号从1到N。每个节点有一个权值。需要维护两种操作：

1.Cix (x^2^31) 表示将节点i的权值变为x^2^31。

2.Q+Description 表示询问树的最大权值。

Description给定一棵N个节点的树，标号从1~N。每个点有一个权值。要求维护两种操作：1.Cix(0x2^31)表示将i点权值变为x2.Q

Description

给定一棵N 个节点的树，标号从1~N。每个点有一个权值。要求维护两种操作： 1. C i x(0<=x<2^31) 表示将i 点权值变为x 2. Q i j x(0<=x<2^31) 表示询问i 到j 的路径上有多少个值为x 的节点

Solution

这是一道很裸的树链剖分的题目，有一道题很这题极其类似旅行 不过多了一些操作而已。

用动态开空间的方法

这种方法又快又好大，没有什么麻烦的操作，全是些基础。

要打个离散化加hash

我是一个c++选手，一个map就搞定了。

注意

root有可能会爆掉，这个坑了我10分，TAT

在线大法好！

Code

#include#include#include#include#include#include#define fo(i,a,b) for(i=a;i<=b;i++)using namespace std;const int maxn=100007;int i,j,k,l,n,m,ans;int first[maxn*2],next[maxn*2],last[maxn*2],num,tot;int size[maxn],fa[maxn],deep[maxn],son[maxn],w[maxn],sum;int root[maxn*6],top[maxn],tt,e[maxn],ppo,b[maxn];bool bz[maxn];map f;char s[5];struct nod{ int a,b,c;}a[maxn];struct node{ int l,r,sum;}t[maxn*200]; void add(int x,int y){ last[++num]=y; next[num]=first[x]; first[x]=num; last[++num]=x; next[num]=first[y]; first[y]=num;}void dfs1(int x,int y){ int i,k=0; size[x]=1; for(i=first[x];i;i=next[i]){ if(last[i]!=y){ fa[last[i]]=x; deep[last[i]]=deep[x]+1; dfs1(last[i],x); size[x]+=size[last[i]]; if(k