Description给定一棵N个节点的树，标号从1~N。每个点有一个权值。要求维护两种操作：1.Cix(0x2^31)表示将i点权值变为x2.Q Description 给定一棵N 个节点的树，标号从1~N。每个点有一个权值。要
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
这是一道很裸的树链剖分的题目，有一道题很这题极其类似【SDOI2014】旅行 不过多了一些操作而已。
用动态开空间的方法
这种方法又快又好大，没有什么麻烦的操作，全是些基础。
要打个离散化加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 上一篇：Tensorflow用别人训练好的模型进行图像分类（可运行）
下一篇：没有了