题目描述 S国有N个城市，编号从1到N。城市间用N-1条双向道路连接，满足
输入 输入的第一行包含整数N，Q依次表示城市数和事件数。
输出 对每个QS和QM事件，输出一行，表示旅行者记下的数字。
样例输入 5 6 样例输出 8 提示 N，Q < =10^5 ， C < =10^5
数据保证对所有QS和QM事件，起点和终点城市的信仰相同；在任意时
如果没有信仰的限制就直接上树链剖分就好了，但有了信仰的限制显然不能把所有点都建在同一棵线段树中，要每种信仰开一棵。但发现信仰最多是105 种，如果开全每棵线段树一定会MLE，因此动态开点，每次修改只加入一个链，查询时在对应信仰的线段树上边跳重链边求值就好了。
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
int n,m;
int x,y;
int num;
int cnt;
int tot;
char ch[10];
int s[100010];
int c[100010];
int v[100010];
int d[100010];
int f[100010];
int to[200010];
int son[100010];
int top[100010];
int ls[4000010];
int rs[4000010];
int mx[4000010];
int sum[4000010];
int size[100010];
int root[100010];
int next[200010];
int head[100010];
void add(int x,int y)
{tot++;next[tot]=head[x];head[x]=tot;to[tot]=y;
}
void dfs(int x,int fa)
{f[x]=fa;d[x]=d[fa]+1;size[x]=1;for(int i=head[x];i;i=next[i]){if(to[i]!=fa){dfs(to[i],x);size[x]+=size[to[i]];if(size[to[i]]>size[son[x]]){son[x]=to[i];}}}
}
void dfs2(int x,int tp)
{top[x]=tp;s[x]=++num;if(son[x]){dfs2(son[x],tp);}for(int i=head[x];i;i=next[i]){if(to[i]!=f[x]&&to[i]!=son[x]){dfs2(to[i],to[i]);}}
}
void updata(int rt)
{sum[rt]=sum[ls[rt]]+sum[rs[rt]];mx[rt]=max(mx[ls[rt]],mx[rs[rt]]);
}
void change(int &rt,int l,int r,int k,int v)
{if(!rt){rt=++cnt;}if(l==r){sum[rt]=v;mx[rt]=v;return ;}int mid=(l+r)>>1;if(k<=mid){change(ls[rt],l,mid,k,v);}else{change(rs[rt],mid+1,r,k,v);}updata(rt);
}
int querysum(int rt,int l,int r,int L,int R)
{if(!rt){return 0;}if(L<=l&&r<=R){return sum[rt];}int mid=(l+r)>>1;int res=0;if(L<=mid){res+=querysum(ls[rt],l,mid,L,R);}if(R>mid){res+=querysum(rs[rt],mid+1,r,L,R);}return res;
}
int querymax(int rt,int l,int r,int L,int R)
{if(!rt){return 0;}if(L<=l&&r<=R){return mx[rt];}int mid=(l+r)>>1;int res=0;if(L<=mid){res=max(res,querymax(ls[rt],l,mid,L,R));}if(R>mid){res=max(res,querymax(rs[rt],mid+1,r,L,R));}return res;
}
int asksum(int rt,int x,int y)
{int res=0;while(top[x]!=top[y]){if(d[top[x]]d[y]){swap(x,y);}res+=querysum(rt,1,n,s[x],s[y]);return res;
}
int askmax(int rt,int x,int y)
{int res=0;while(top[x]!=top[y]){if(d[top[x]]d[y]){swap(x,y);}res=max(res,querymax(rt,1,n,s[x],s[y]));return res;
}
int main()
{scanf("%d%d",&n,&m);for(int i=1;i<=n;i++){scanf("%d%d",&v[i],&c[i]);}for(int i=1;i 转载于:https://www.cnblogs.com/Khada-Jhin/p/9562260.html
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】 进行投诉反馈！
