费了一番功夫，神犇 CJK 终于完成了前三道题目。“不错，不愧是新一代神犇 啊！” JesseLiu 满意地说道，“不过，你在算法方面的功底固然不错。对于数据结 构的运用，你又掌握地如何呢？” 听到“数据结构”这四个字，就连身为神犇的 CJK 也不禁吓出一身冷汗。“年轻 人，现在，对于我给定一棵树，你需要完成以下操作： 1.修改某个点的权值； 2.查询某两点间路径上所有点的权值和； 3.查询某点子树的权值和。” CJK 脸上闪过一丝不屑：不就是道链剖裸题吗？ “这只是第一问。”JesseLiu 似乎也觉得这道题太水了，于是补充道：“完成以 上所有操作后，我还会有以下几种询问： 1. 询问某个点子树上有多少个点的权值小于等于 k； 2. 询问某两点之间的路径上有多少点的权值小于等于 k；” 尽管 CJK 是神犇，但遇到这种题，也不禁感到一丝恐惧。还好，通过自己的 玄学力量，他联系到了他的同学——你。现在，就请你 A 掉这最后一道水题。
第一行一个数 n，表示点的总数。接下来 n-1 行，一行两个整数 x 和 y，表示 x 和 y 之间有边相连。接下来一个整数 m1，表示第一问中操作的数量。接下来 m1 行表示操作，格式如下： “1 x y”将点 x 的权值修改为 y； “2 x y”询问 x 到 y 路径上的点权之和（包括 x 和 y）； “3 x”询问 x 的子树上的点权和（包括 x）； 接下来一行 m2，表示第二问中操作的数量。接下来 m2 行描述操作，格式 如下： “1 x y z”询问 x 到 y 的路径上有多少个点的权值小于等于 z； “2 x y”询问 x 的子树上有多少个点的权值小于等于 y； 每个点的初始权值为 0,默认树根为 1 号节点。
对于每一次询问，输出一个整数表示询问的答案。
样例①：
3 1 2 1 3 3 1 1 3 1 3 1 3 1 2 2 1 2 1 1 3 1
样例②：
5 1 2 1 3 3 4 3 5 5 3 1 1 3 1 2 4 5 1 4 -1 3 3 2 1 1 5 0 2 3 -1
样例①：
4 2 1
样例②：
0 1 0 2 1
对于 30%的数据，n<=100,m1<=100,m2<=100。剩下的数据保证 n<=50000； 对于另外 30%的数据，m2=0。其中有 1 组数据，树退化为链; 对于 100%的数据， 保证 n<=50000,m1<=50000,m2<=50000， 保证题目中所有输入、 输出、中间运算不超过 int 范围。
叶闻捷出题 NOIP 模拟测试T4
这道题的第一问是一个树链剖分，在此就不作赘述了。 对于第二问，我们可以采取一种离线算法： 先将线段树中的值清空，然后将询问与添加操作放入一个数组，按询问（添加）的值从小到大排序，然后按顺序一个一个询问（添加），这样可以保证在询问时，线段树中的值都小于等于k。
代码#include <cstring>#include <cmath>#include <iostream>#include <cstdio>#include <algorithm>#define lson num<<1#define rson num<<1|1using namespace std;typedef long long ll;const int maxn = 50010;int cnt, tt, n;int a[maxn], dfn[maxn], l[maxn*4], r[maxn*4], ch[maxn], top[maxn], to[maxn*2], sz[maxn];int nxt[maxn*2], head[maxn],ed[maxn], id[maxn], father[maxn], dep[maxn],tr[maxn*4], ans[maxn];struct tree_node { int x, y, z, id, t;}g[maxn*3];inline void dfs1(int x,int d) { dep[x] = d,sz[x] = 1; for(int i = head[x]; i; i = nxt[i]) if(!dep[to[i]]) { dfs1(to[i] ,d + 1),sz[x] += sz[to[i]],father[to[i]]=x; if(sz[to[i]]>sz[ch[x]]) ch[x]=to[i]; }}inline void dfs2(int x,int f) { top[x]=f,dfn[x]=++cnt; if(ch[x]) dfs2(ch[x],f); for(int i=head[x]; i; i=nxt[i]) if(to[i]!=father[x]&&to[i]!=ch[x]) dfs2(to[i],to[i]); ed[x]=cnt;}inline void update(int x,int y,int l,int r,int num) { if(l==r) {tr[num]=y;return;} int mid=(l+r)>>1; if(x<=mid) update(x,y,l,mid,lson); else update(x,y,mid+1,r,rson); tr[num]=tr[lson]+tr[rson];}inline int query(int L,int R,int l,int r,int num) { if(L<=l&&r<=R) return tr[num]; int mid=(l+r)>>1; ll ret=0; if(L<=mid) ret+=query(L,R,l,mid,lson); if(R>mid) ret+=query(L,R,mid+1,r,rson); return ret;}inline int lca(int x,int y) { int ans=0; while(top[x]!=top[y]) { if(dep[top[x]]<dep[top[y]]) swap(x,y); ans+=query(dfn[top[x]],dfn[x],1,n,1); x=father[top[x]]; } if(dep[x]>dep[y]) swap(x,y); ans+=query(dfn[x],dfn[y],1,n,1); return ans;}inline bool cmp(const tree_node x,const tree_node y) { if(x.z!=y.z) return x.z<y.z; return x.id<y.id; }int main() { freopen("input.in", "r", stdin); freopen("output.out", "w", stdout); int m, flag, x, y; scanf("%d", &n); for(int i = 1; i < n; i++) { scanf("%d%d", &x, &y); to[++tt] = y,nxt[tt] = head[x], head[x] = tt; to[++tt] = x,nxt[tt] = head[y], head[y] = tt; } dfs1(1, 1),dfs2(1, 1); scanf("%d", &m); for(int i = 1; i <= m; i++) { scanf("%d", &flag); if(flag == 1) scanf("%d%d", &x, &y), update(dfn[x], y, 1, n, 1); else if(flag == 2) scanf("%d%d", &x, &y), PRintf("%d/n", lca(x, y)); else { scanf("%d", &x); printf("%d/n", query(dfn[x], ed[x], 1, n, 1)); } } scanf("%d", &m); for(int i=1;i<=m;i++) { scanf("%d", &g[i].id),g[i].t=i; if(g[i].id==1) scanf("%d%d%d", &g[i].x, &g[i].y, &g[i].z); else scanf("%d%d", &g[i].x, &g[i].z); } for(int i=1;i<=n;i++) g[++m].id=0,g[m].x=dfn[i],g[m].z=query(dfn[i],dfn[i],1,n,1); memset(tr,0,sizeof(tr)); sort(g+1,g+1+m,cmp); for(int i=1;i<=m;i++) { if(g[i].id==0) update(g[i].x,1,1,n,1); else if(g[i].id==1) ans[g[i].t]=lca(g[i].x,g[i].y); else ans[g[i].t]=query(dfn[g[i].x],ed[g[i].x],1,n,1); } for(int i=1;i<=m-n;i++) printf("%d/n",ans[i]); return 0;}新闻热点
疑难解答
