这真是个神奇的东西。
一、模板例题：
P3384 【模板】树链剖分：
题目描述
如题，已知一棵包含N个结点的树（连通且无环），每个节点上包含一个数值，需要支持以下操作：
操作1： 格式： 1 x y z 表示将树从x到y结点最短路径上所有节点的值都加上z
操作2： 格式： 2 x y 表示求树从x到y结点最短路径上所有节点的值之和
操作3： 格式： 3 x z 表示将以x为根节点的子树内所有节点值都加上z
操作4： 格式： 4 x 表示求以x为根节点的子树内所有节点值之和
输入格式
第一行包含4个正整数N、M、R、P，分别表示树的结点个数、操作个数、根节点序号和取模数（即所有的输出结果均对此取模）。
接下来一行包含N个非负整数，分别依次表示各个节点上初始的数值。
接下来N-1行每行包含两个整数x、y，表示点x和点y之间连有一条边（保证无环且连通）
接下来M行每行包含若干个正整数，每行表示一个操作，格式如下：
操作1： 1 x y z
操作2： 2 x y
操作3： 3 x z
操作4： 4 x
输出格式
输出包含若干行，分别依次表示每个操作2或操作4所得的结果（对P取模）
输入输出样例
输入 #1 复制
5 5 2 24
7 3 7 8 0
1 2
1 5
3 1
4 1
3 4 2
3 2 2
4 5
1 5 1 3
2 1 3
输出 #1 复制
2
21
说明/提示
时空限制：1s，128M
数据规模：
n<=1e5,m<=1e5
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#include<set>
#include<vector>
#define ll long long
#define llu unsigned ll
using namespace std;
const ll lnf=0x3f3f3f3f3f3f3f3f;
const int maxn=100100;
int n,m,r,k;
int head[maxn],ver[maxn<<1],nt[maxn<<1];
int f[maxn],d[maxn],si[maxn],son[maxn],rk[maxn];
int top[maxn],id[maxn],vi[maxn];
int tot=1,cnt=0;
void add(int x,int y)
{
ver[++tot]=y,nt[tot]=head[x],head[x]=tot;
}
void dfs1(int x,int fa)
{
int max_son=0;
si[x]=1;
for(int i=head[x];i;i=nt[i])
{
int y=ver[i];
if(y==fa) continue;
f[y]=x;
d[y]=d[x]+1;
dfs1(y,x);
si[x]+=si[y];
if(si[y]>max_son)max_son=si[y],son[x]=y;
}
}
void dfs2(int x,int t)
{
top[x]=t;
id[x]=++cnt;
rk[cnt]=x;
if(!son[x]) return ;
dfs2(son[x],t);
for(int i=head[x];i;i=nt[i])
{
int y=ver[i];
if(y!=son[x]&&y!=f[x])
dfs2(y,y);
}
}
struct node
{
int l,r;
ll sum;
ll laz;
}t[maxn<<2];
void pushup(int cnt)
{
t[cnt].sum=(t[cnt<<1].sum+t[cnt<<1|1].sum)%k;
}
void pushdown(int cnt)
{
if(t[cnt].laz)
{
t[cnt<<1].sum=(t[cnt<<1].sum+(t[cnt<<1].r-t[cnt<<1].l+1)*t[cnt].laz)%k;
t[cnt<<1|1].sum=(t[cnt<<1|1].sum+(t[cnt<<1|1].r-t[cnt<<1|1].l+1)*t[cnt].laz)%k;
t[cnt<<1].laz=(t[cnt<<1].laz+t[cnt].laz)%k;
t[cnt<<1|1].laz=(t[cnt<<1|1].laz+t[cnt].laz)%k;
t[cnt].laz=0;
}
}
void build(int l,int r,int cnt)
{
t[cnt].l=l,t[cnt].r=r;
t[cnt].laz=0;
if(l==r)
{
t[cnt].sum=vi[rk[l]]%k;
return ;
}
int mid=(l+r)>>1;
build(l,mid,cnt<<1);
build(mid+1,r,cnt<<1|1);
pushup(cnt);
}
void change(int l,int r,ll val,int cnt)
{
if(l<=t[cnt].l&&t[cnt].r<=r)
{
t[cnt].sum=(t[cnt].sum+(t[cnt].r-t[cnt].l+1)*val)%k;
t[cnt].laz=(t[cnt].laz+val)%k;
return ;
}
pushdown(cnt);
if(l<=t[cnt<<1].r) change(l,r,val,cnt<<1);
if(r>=t[cnt<<1|1].l) change(l,r,val,cnt<<1|1);
pushup(cnt);
}
ll ask(int l,int r,int cnt)
{
if(l<=t[cnt].l&&t[cnt].r<=r)
{
return t[cnt].sum;
}
pushdown(cnt);
ll ans=0;
if(l<=t[cnt<<1].r) ans+=ask(l,r,cnt<<1);
if(r>=t[cnt<<1|1].l) ans+=ask(l,r,cnt<<1|1);
return ans%k;
}
void changeroad(int x,int y,ll val)
{
val%=k;
while(top[x]!=top[y])
{
if(d[top[x]]<d[top[y]])
swap(x,y);
change(id[top[x]],id[x],val,1);
x=f[top[x]];
}
if(id[x]>id[y]) swap(x,y);
change(id[x],id[y],val,1);
}
void changetree(int x,int val)
{
change(id[x],id[x]+si[x]-1,val,1);
}
void askroad(int x,int y)
{
ll ans=0;
while(top[x]!=top[y])
{
if(d[top[x]]<d[top[y]])
swap(x,y);
ans=(ans+ask(id[top[x]],id[x],1))%k;
x=f[top[x]];
}
if(id[x]>id[y]) swap(x,y);
ans=(ans+ask(id[x],id[y],1))%k;
printf("%lld\n",ans);
}
void asktree(int x)
{
printf("%lld\n",ask(id[x],id[x]+si[x]-1,1));
}
int main(void)
{
scanf("%d%d%d%d",&n,&m,&r,&k);
for(int i=1;i<=n;i++)
scanf("%d",&vi[i]);
int pos,x,y,z;
for(int i=1;i<n;i++)
{
scanf("%d%d",&x,&y);
add(x,y);
add(y,x);
}
dfs1(r,0);
dfs2(r,r);
build(1,cnt,1);
//cout<<cnt<<endl;
for(int i=1;i<=m;i++)
{
scanf("%d",&pos);
if(pos==1)
{
scanf("%d%d%d",&x,&y,&z);
changeroad(x,y,z);
}
else if(pos==2)
{
scanf("%d%d",&x,&y);
askroad(x,y);
}
else if(pos==3)
{
scanf("%d%d",&x,&z);
changetree(x,z);
}
else if(pos==4)
{
scanf("%d",&x);
asktree(x);
}
}
return 0;
}
这个树链剖分以前还以为多高大上，实际上也就那样。。
二、P2590 [ZJOI2008]树的统计：
题目描述
一棵树上有n个节点，编号分别为1到n，每个节点都有一个权值w。
我们将以下面的形式来要求你对这棵树完成一些操作：
I. CHANGE u t : 把结点u的权值改为t
II. QMAX u v: 询问从点u到点v的路径上的节点的最大权值
III. QSUM u v: 询问从点u到点v的路径上的节点的权值和
注意：从点u到点v的路径上的节点包括u和v本身
输入格式
输入文件的第一行为一个整数n，表示节点的个数。
接下来n – 1行，每行2个整数a和b，表示节点a和节点b之间有一条边相连。
接下来一行n个整数，第i个整数wi表示节点i的权值。
接下来1行，为一个整数q，表示操作的总数。
接下来q行，每行一个操作，以“CHANGE u t”或者“QMAX u v”或者“QSUM u v”的形式给出。
输出格式
对于每个“QMAX”或者“QSUM”的操作，每行输出一个整数表示要求输出的结果。
输入输出样例
输入 #1 复制
4
1 2
2 3
4 1
4 2 1 3
12
QMAX 3 4
QMAX 3 3
QMAX 3 2
QMAX 2 3
QSUM 3 4
QSUM 2 1
CHANGE 1 5
QMAX 3 4
CHANGE 3 6
QMAX 3 4
QMAX 2 4
QSUM 3 4
输出 #1 复制
4
1
2
2
10
6
5
6
5
16
说明/提示
对于100％的数据，保证1<=n<=30000，0<=q<=200000；中途操作中保证每个节点的权值w在-30000到30000之间。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#include<set>
#include<vector>
#define ll long long
#define llu unsigned ll
using namespace std;
const ll lnf=0x3f3f3f3f3f3f3f3f;
const int inf=0x3f3f3f3f;
const int maxn=30100;
char str[20];
int n,q;
int head[maxn],ver[maxn<<1],nt[maxn<<1];
int d[maxn],f[maxn],si[maxn],son[maxn];
int id[maxn],top[maxn],rk[maxn];
ll vi[maxn];
int tot=1,cnt=0;
void add(int x,int y)
{
ver[++tot]=y,nt[tot]=head[x],head[x]=tot;
}
void dfs1(int x,int fa)
{
si[x]=1;
int max_son=0;
for(int i=head[x];i;i=nt[i])
{
int y=ver[i];
if(y==fa) continue;
d[y]=d[x]+1;
f[y]=x;
dfs1(y,x);
si[x]+=si[y];
if(si[y]>max_son) max_son=si[y],son[x]=y;
}
}
void dfs2(int x,int t)
{
top[x]=t;
id[x]=++cnt;
rk[cnt]=x;
if(!son[x]) return ;
dfs2(son[x],t);
for(int i=head[x];i;i=nt[i])
{
int y=ver[i];
if(y!=son[x]&&y!=f[x])
dfs2(y,y);
}
}
struct node
{
int l,r;
ll sum;
ll maxx;
}t[maxn<<2];
void pushup(int cnt)
{
t[cnt].sum=t[cnt<<1].sum+t[cnt<<1|1].sum;
t[cnt].maxx=max(t[cnt<<1].maxx,t[cnt<<1|1].maxx);
}
void build(int l,int r,int cnt)
{
t[cnt].l=l,t[cnt].r=r;
if(l==r)
{
t[cnt].sum=t[cnt].maxx=vi[rk[l]];
return ;
}
int mid=(l+r)>>1;
build(l,mid,cnt<<1);
build(mid+1,r,cnt<<1|1);
pushup(cnt);
}
void change(int pos,ll val,int cnt)
{
if(t[cnt].l==t[cnt].r)
{
t[cnt].maxx=t[cnt].sum=val;
return ;
}
if(pos<=t[cnt<<1].r) change(pos,val,cnt<<1);
else change(pos,val,cnt<<1|1);
pushup(cnt);
}
ll ask_sum(int l,int r,int cnt)
{
if(l<=t[cnt].l&&t[cnt].r<=r)
{
return t[cnt].sum;
}
ll ans=0;
if(l<=t[cnt<<1].r) ans+=ask_sum(l,r,cnt<<1);
if(r>=t[cnt<<1|1].l) ans+=ask_sum(l,r,cnt<<1|1);
return ans;
}
ll ask_max(int l,int r,int cnt)
{
if(l<=t[cnt].l&&t[cnt].r<=r)
{
return t[cnt].maxx;
}
ll ans=-lnf;
if(l<=t[cnt<<1].r) ans=max(ans,ask_max(l,r,cnt<<1));
if(r>=t[cnt<<1|1].l) ans=max(ans,ask_max(l,r,cnt<<1|1));
return ans;
}
ll ask_road_sum(int x,int y)
{
ll ans=0;
while(top[x]!=top[y])
{
if(d[top[x]]<d[top[y]])
swap(x,y);
ans+=ask_sum(id[top[x]],id[x],1);
x=f[top[x]];
}
if(id[x]>id[y])
swap(x,y);
ans+=ask_sum(id[x],id[y],1);
return ans;
}
ll ask_road_max(int x,int y)
{
ll ans=-lnf;
while(top[x]!=top[y])
{
if(d[top[x]]<d[top[y]])
swap(x,y);
ans=max(ans,ask_max(id[top[x]],id[x],1));
x=f[top[x]];
}
if(id[x]>id[y])swap(x,y);
return max(ans,ask_max(id[x],id[y],1));
}
int main(void)
{
scanf("%d",&n);
int x,y;
for(int i=1;i<n;i++)
{
scanf("%d%d",&x,&y);
add(x,y);
add(y,x);
}
for(int i=1;i<=n;i++)
scanf("%lld",&vi[i]);
dfs1(1,0);
dfs2(1,1);
build(1,cnt,1);
scanf("%d",&q);
for(int i=1;i<=q;i++)
{
scanf("%s",str);
if(str[0]=='C')
{
scanf("%d%d",&x,&y);
change(id[x],y,1);
}
else if(str[1]=='M')
{
scanf("%d%d",&x,&y);
printf("%lld\n",ask_road_max(x,y));
}
else
{
scanf("%d%d",&x,&y);
printf("%lld\n",ask_road_sum(x,y));
}
}
return 0;
}
三、P4315 月下“毛景树”：
题目描述
毛毛虫经过及时的变形，最终逃过的一劫，离开了菜妈的菜园。 毛毛虫经过千山万水，历尽千辛万苦，最后来到了小小的绍兴一中的校园里。
爬啊爬爬啊爬毛毛虫爬到了一颗小小的“毛景树”下面，发现树上长着他最爱吃的毛毛果 “毛景树”上有N个节点和N-1条树枝，但节点上是没有毛毛果的，毛毛果都是长在树枝上的。但是这棵“毛景树”有着神奇的魔力，他能改变树枝上毛毛果的个数：
Change k w：将第k条树枝上毛毛果的个数改变为w个。
Cover u v w：将节点u与节点v之间的树枝上毛毛果的个数都改变为w个。
Add u v w：将节点u与节点v之间的树枝上毛毛果的个数都增加w个。 由于毛毛虫很贪，于是他会有如下询问：
Max u v：询问节点u与节点v之间树枝上毛毛果个数最多有多少个。
输入格式
第一行一个正整数N。
接下来N-1行，每行三个正整数Ui，Vi和Wi，第i+1行描述第i条树枝。表示第i条树枝连接节点Ui和节点Vi，树枝上有Wi个毛毛果。 接下来是操作和询问，以“Stop”结束。
输出格式
对于毛毛虫的每个询问操作，输出一个答案。
输入输出样例
输入 #1 复制
4
1 2 8
1 3 7
3 4 9
Max 2 4
Cover 2 4 5
Add 1 4 10
Change 1 16
Max 2 4
Stop
输出 #1 复制
9
16
说明/提示
1<=N<=100,000，操作+询问数目不超过100,000。
保证在任意时刻，所有树枝上毛毛果的个数都不会超过10^9个。
这个题改变的边权，那么我们就可以考虑把某个点与其父亲结点之间边的边权转化为这个点的点权。
注意laz标记的顺序。
注意当x，y在一条链中时，我们应该让深度较低的那个+1。
如果x，y深度相等时，则不应该再计算。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#include<set>
#include<vector>
#define ll long long
#define llu unsigned ll
using namespace std;
const ll lnf=0x3f3f3f3f3f3f3f3f;
const int inf=0x3f3f3f3f;
const int maxn=100100;
char str[20];
int n,q;
int head[maxn],ver[maxn<<1],edge[maxn<<1],nt[maxn<<1];
int d[maxn],f[maxn],si[maxn],son[maxn];
int id[maxn],top[maxn],rk[maxn];
int tot=1,cnt=0;
int vi[maxn],ed[maxn],match[maxn];
void add(int x,int y,int z,int i)
{
ver[++tot]=y,edge[tot]=z,nt[tot]=head[x],head[x]=tot,ed[tot]=i;
}
void dfs1(int x,int fa)
{
si[x]=1;
int max_son=0;
for(int i=head[x];i;i=nt[i])
{
int y=ver[i],z=edge[i];
if(y==fa) continue;
d[y]=d[x]+1;
f[y]=x;
vi[y]=z;
match[ed[i]]=y;
dfs1(y,x);
si[x]+=si[y];
if(si[y]>max_son) max_son=si[y],son[x]=y;
}
}
void dfs2(int x,int t)
{
top[x]=t;
id[x]=++cnt;
rk[cnt]=x;
if(!son[x]) return ;
dfs2(son[x],t);
for(int i=head[x];i;i=nt[i])
{
int y=ver[i];
if(y!=son[x]&&y!=f[x])
dfs2(y,y);
}
}
struct node
{
int l,r;
int maxx;
int laz_add;
int laz_change;
}t[maxn<<2];
void pushup(int cnt)
{
t[cnt].maxx=max(t[cnt<<1].maxx,t[cnt<<1|1].maxx);
}
void pushdown(int cnt)
{
if(t[cnt].laz_change!=-inf)
{
t[cnt<<1].laz_add=t[cnt<<1|1].laz_add=0;
t[cnt<<1].laz_change=t[cnt<<1|1].laz_change=t[cnt].laz_change;
t[cnt<<1].maxx=t[cnt<<1|1].maxx=t[cnt].laz_change;
t[cnt].laz_change=-inf;
}
if(t[cnt].laz_add)
{
t[cnt<<1].maxx+=t[cnt].laz_add;
t[cnt<<1|1].maxx+=t[cnt].laz_add;
t[cnt<<1].laz_add+=t[cnt].laz_add;
t[cnt<<1|1].laz_add+=t[cnt].laz_add;
t[cnt].laz_add=0;
}
}
void build(int l,int r,int cnt)
{
t[cnt].l=l,t[cnt].r=r;
t[cnt].laz_add=0,t[cnt].laz_change=-inf;
if(l==r)
{
t[cnt].maxx=vi[rk[l]];
return ;
}
int mid=(l+r)>>1;
build(l,mid,cnt<<1);
build(mid+1,r,cnt<<1|1);
pushup(cnt);
}
void change(int pos,int val,int cnt)
{
if(t[cnt].l==t[cnt].r)
{
t[cnt].maxx=val;
return ;
}
pushdown(cnt);
if(pos<=t[cnt<<1].r) change(pos,val,cnt<<1);
else change(pos,val,cnt<<1|1);
pushup(cnt);
}
void change_add(int l,int r,int val,int cnt)
{
if(l<=t[cnt].l&&t[cnt].r<=r)
{
t[cnt].maxx+=val;
t[cnt].laz_add+=val;
return ;
}
pushdown(cnt);
if(l<=t[cnt<<1].r) change_add(l,r,val,cnt<<1);
if(r>=t[cnt<<1|1].l) change_add(l,r,val,cnt<<1|1);
pushup(cnt);
}
void change_all(int l,int r,int val,int cnt)
{
if(l<=t[cnt].l&&t[cnt].r<=r)
{
t[cnt].maxx=val;
t[cnt].laz_change=val;
t[cnt].laz_add=0;
return ;
}
pushdown(cnt);
if(l<=t[cnt<<1].r) change_all(l,r,val,cnt<<1);
if(r>=t[cnt<<1|1].l) change_all(l,r,val,cnt<<1|1);
pushup(cnt);
}
int ask(int l,int r,int cnt)
{
if(l<=t[cnt].l&&t[cnt].r<=r)
{
return t[cnt].maxx;
}
pushdown(cnt);
int ans=-inf;
if(l<=t[cnt<<1].r) ans=max(ans,ask(l,r,cnt<<1));
if(r>=t[cnt<<1|1].l) ans=max(ans,ask(l,r,cnt<<1|1));
return ans;
}
void change_road_add(int x,int y,int val)
{
while(top[x]!=top[y])
{
if(d[top[x]]<d[top[y]])
swap(x,y);
change_add(id[top[x]],id[x],val,1);
x=f[top[x]];
}
if(id[x]>id[y])
swap(x,y);
if(id[x]!=id[y]) change_add(id[x]+1,id[y],val,1);
}
void change_road_all(int x,int y,int val)
{
while(top[x]!=top[y])
{
if(d[top[x]]<d[top[y]])
swap(x,y);
change_all(id[top[x]],id[x],val,1);
x=f[top[x]];
}
if(id[x]>id[y])
swap(x,y);
if(id[x]!=id[y]) change_all(id[x]+1,id[y],val,1);
}
int ask_road_max(int x,int y)
{
int ans=-inf;
while(top[x]!=top[y])
{
if(d[top[x]]<d[top[y]])
swap(x,y);
ans=max(ans,ask(id[top[x]],id[x],1));
x=f[top[x]];
}
if(id[x]>id[y])
swap(x,y);
if(id[x]!=id[y]) ans=max(ans,ask(id[x]+1,id[y],1));
return ans;
}
int main(void)
{
scanf("%d",&n);
int x,y,z;
for(int i=1;i<n;i++)
{
scanf("%d%d%d",&x,&y,&z);
add(x,y,z,i);
add(y,x,z,i);
}
dfs1(1,0);
dfs2(1,1);
build(1,cnt,1);
while(scanf("%s",str),str[0]!='S')
{
if(str[0]=='M')
{
scanf("%d%d",&x,&y);
printf("%d\n",ask_road_max(x,y));
}
else if(str[0]=='A')
{
scanf("%d%d%d",&x,&y,&z);
change_road_add(x,y,z);
}
//这里两种x边对应的id是什么的处理方式。
/*else if(str[1]=='h') { scanf("%d%d",&x,&z); //x=d[ver[x*2]]>d[ver[x*2+1]]?ver[x*2]:ver[x*2+1]; change(id[match[x]],z,1); }*/
else if(str[1]=='h')
{
scanf("%d%d",&x,&z);
x=d[ver[x*2]]>d[ver[x*2+1]]?ver[x*2]:ver[x*2+1];
change(id[x],z,1);
}
else if(str[1]=='o')
{
scanf("%d%d%d",&x,&y,&z);
change_road_all(x,y,z);
}
}
return 0;
}
四、P3833 [SHOI2012]魔法树：
题目背景
SHOI2012 D2T3
题目描述
Harry Potter 新学了一种魔法：可以让改变树上的果子个数。满心欢喜的他找到了一个巨大的果树，来试验他的新法术。
这棵果树共有N个节点，其中节点0是根节点，每个节点u的父亲记为fa[u]，保证有fa[u] < u。初始时，这棵果树上的果子都被 Dumbledore 用魔法清除掉了，所以这个果树的每个节点上都没有果子（即0个果子）。
不幸的是，Harry 的法术学得不到位，只能对树上一段路径的节点上的果子个数统一增加一定的数量。也就是说，Harry 的魔法可以这样描述：
Add u v d
表示将点u和v之间的路径上的所有节点的果子个数都加上d。
接下来，为了方便检验 Harry 的魔法是否成功，你需要告诉他在释放魔法的过程中的一些有关果树的信息：
Query u
表示当前果树中，以点u为根的子树中，总共有多少个果子？
输入格式
第一行一个正整数N (1 ≤ N ≤ 100000)，表示果树的节点总数，节点以0,1,…,N − 1标号，0一定代表根节点。
接下来N − 1行，每行两个整数a,b (0 ≤ a < b < N)，表示a是b的父亲。
接下来是一个正整数Q(1 ≤ ? ≤ 100000)，表示共有Q次操作。
后面跟着Q行，每行是以下两种中的一种：
A u v d，表示将u到v的路径上的所有节点的果子数加上d；0 ≤ u,v <N,0 < d < 100000
Q u，表示询问以u为根的子树中的总果子数，注意是包括u本身的。
输出格式
对于所有的Query操作，依次输出询问的答案，每行一个。答案可能会超过2^32 ，但不会超过10^15 。
输入输出样例
输入 #1 复制
4
0 1
1 2
2 3
4
A 1 3 1
Q 0
Q 1
Q 2
输出 #1 复制
3
3
2
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#include<set>
#include<vector>
#define ll long long
#define llu unsigned ll
using namespace std;
const ll lnf=0x3f3f3f3f3f3f3f3f;
const int inf=0x3f3f3f3f;
const int maxn=100100;
int n,q;
char str[20];
int head[maxn],ver[maxn<<1],nt[maxn<<1];
int f[maxn],d[maxn],si[maxn],son[maxn];
int id[maxn],top[maxn],rk[maxn];
int tot=1,cnt=0;
void add(int x,int y)
{
ver[++tot]=y,nt[tot]=head[x],head[x]=tot;
}
void dfs1(int x,int fa)
{
int max_son=0;
si[x]=1;
for(int i=head[x];i;i=nt[i])
{
int y=ver[i];
if(y==fa) continue;
d[y]=d[x]+1;
f[y]=x;
dfs1(y,x);
si[x]+=si[y];
if(si[y]>max_son) max_son=si[y],son[x]=y;
}
}
void dfs2(int x,int t)
{
top[x]=t;
id[x]=++cnt;
rk[cnt]=x;
if(!son[x]) return ;
dfs2(son[x],t);
for(int i=head[x];i;i=nt[i])
{
int y=ver[i];
if(y!=son[x]&&y!=f[x])
dfs2(y,y);
}
}
struct node
{
int l,r;
ll sum;
ll laz;
}t[maxn<<2];
void pushup(int cnt)
{
t[cnt].sum=(t[cnt<<1].sum+t[cnt<<1|1].sum);
}
void pushdown(int cnt)
{
if(t[cnt].laz)
{
t[cnt<<1].sum+=(t[cnt<<1].r-t[cnt<<1].l+1)*t[cnt].laz;
t[cnt<<1|1].sum+=(t[cnt<<1|1].r-t[cnt<<1|1].l+1)*t[cnt].laz;
t[cnt<<1].laz+=t[cnt].laz;
t[cnt<<1|1].laz+=t[cnt].laz;
t[cnt].laz=0;
}
}
void build(int l,int r,int cnt)
{
t[cnt].l=l,t[cnt].r=r;
t[cnt].laz=0,t[cnt].sum=0;
if(l==r) return ;
int mid=(l+r)>>1;
build(l,mid,cnt<<1);
build(mid+1,r,cnt<<1|1);
}
void change(int l,int r,ll val,int cnt)
{
if(l<=t[cnt].l&&t[cnt].r<=r)
{
t[cnt].sum+=(t[cnt].r-t[cnt].l+1)*val;
t[cnt].laz+=val;
return ;
}
pushdown(cnt);
if(l<=t[cnt<<1].r) change(l,r,val,cnt<<1);
if(r>=t[cnt<<1|1].l) change(l,r,val,cnt<<1|1);
pushup(cnt);
}
ll ask(int l,int r,int cnt)
{
if(l<=t[cnt].l&&t[cnt].r<=r)
{
return t[cnt].sum;
}
pushdown(cnt);
ll ans=0;
if(l<=t[cnt<<1].r) ans+=ask(l,r,cnt<<1);
if(r>=t[cnt<<1|1].l) ans+=ask(l,r,cnt<<1|1);
return ans;
}
void change_road(int x,int y,ll z)
{
while(top[x]!=top[y])
{
if(d[top[x]]<d[top[y]])
swap(x,y);
change(id[top[x]],id[x],z,1);
x=f[top[x]];
}
if(id[x]>id[y]) swap(x,y);
change(id[x],id[y],z,1);
}
int main(void)
{
scanf("%d",&n);
int x,y,z;
for(int i=1;i<n;i++)
{
scanf("%d%d",&x,&y);
x++,y++;
add(x,y);
add(y,x);
}
dfs1(1,0);
dfs2(1,1);
build(1,cnt,1);
scanf("%d",&q);
for(int i=1;i<=q;i++)
{
scanf("%s",str);
if(str[0]=='A')
{
scanf("%d%d%d",&x,&y,&z);
x++,y++;
change_road(x,y,z);
}
else
{
scanf("%d",&x);
x++;
printf("%lld\n",ask(id[x],id[x]+si[x]-1,1));
}
}
return 0;
}
五、P3178 [HAOI2015]树上操作：
题目描述
有一棵点数为 N 的树，以点 1 为根，且树点有边权。然后有 M 个操作，分为三种：
操作 1 ：把某个节点 x 的点权增加 a 。
操作 2 ：把某个节点 x 为根的子树中所有点的点权都增加 a 。
操作 3 ：询问某个节点 x 到根的路径中所有点的点权和。
输入格式
第一行包含两个整数 N, M 。表示点数和操作数。
接下来一行 N 个整数，表示树中节点的初始权值。
接下来 N-1 行每行两个正整数 from, to ， 表示该树中存在一条边 (from, to) 。
再接下来 M 行，每行分别表示一次操作。其中第一个数表示该操作的种类（ 1-3 ） ，之后接这个操作的参数（ x 或者 x a ） 。
输出格式
对于每个询问操作，输出该询问的答案。答案之间用换行隔开。
输入输出样例
输入 #1 复制
5 5
1 2 3 4 5
1 2
1 4
2 3
2 5
3 3
1 2 1
3 5
2 1 2
3 3
输出 #1 复制
6
9
13
说明/提示
对于 100% 的数据， N,M<=100000 ，且所有输入数据的绝对值都不会超过 10^6 。
其实本题可以用dfs序加线段树nlogn解决。
可以看出，增加一个节点的权值会对以它为根的整棵子树都有影响，相当于给整棵子树增加一个值。
而给以某一节点 x 为根的子树增加一个权值也会影响当前子树，节点 y 所增加的值为 dis[y] * z - (dis[x] - 1) * z，每个节点都会增加
-(dis[x] - 1) * z ，询问时只用加上 dis[y] * sum（y）（其中sum（y）为每次的z的和） 和当前节点 y 的权值。
dis数组可以预处理出来。
但是为了联系树剖，就用树剖写了。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#include<set>
#include<vector>
#define ll long long
#define llu unsigned ll
using namespace std;
const ll lnf=0x3f3f3f3f3f3f3f3f;
const int inf=0x3f3f3f3f;
const int maxn=100100;
int n,q;
char str[20];
int head[maxn],ver[maxn<<1],nt[maxn<<1];
int f[maxn],d[maxn],si[maxn],son[maxn];
int id[maxn],top[maxn],rk[maxn];
int vi[maxn];
int tot=1,cnt=0;
void add(int x,int y)
{
ver[++tot]=y,nt[tot]=head[x],head[x]=tot;
}
void dfs1(int x,int fa)
{
int max_son=0;
si[x]=1;
for(int i=head[x];i;i=nt[i])
{
int y=ver[i];
if(y==fa) continue;
d[y]=d[x]+1;
f[y]=x;
dfs1(y,x);
si[x]+=si[y];
if(si[y]>max_son) max_son=si[y],son[x]=y;
}
}
void dfs2(int x,int t)
{
top[x]=t;
id[x]=++cnt;
rk[cnt]=x;
if(!son[x]) return ;
dfs2(son[x],t);
for(int i=head[x];i;i=nt[i])
{
int y=ver[i];
if(y!=son[x]&&y!=f[x])
dfs2(y,y);
}
}
struct node
{
int l,r;
ll sum;
ll laz;
}t[maxn<<2];
void pushup(int cnt)
{
t[cnt].sum=(t[cnt<<1].sum+t[cnt<<1|1].sum);
}
void pushdown(int cnt)
{
if(t[cnt].laz)
{
t[cnt<<1].sum+=(t[cnt<<1].r-t[cnt<<1].l+1)*t[cnt].laz;
t[cnt<<1|1].sum+=(t[cnt<<1|1].r-t[cnt<<1|1].l+1)*t[cnt].laz;
t[cnt<<1].laz+=t[cnt].laz;
t[cnt<<1|1].laz+=t[cnt].laz;
t[cnt].laz=0;
}
}
void build(int l,int r,int cnt)
{
t[cnt].l=l,t[cnt].r=r;
t[cnt].laz=0,t[cnt].sum=0;
if(l==r)
{
t[cnt].sum=vi[rk[l]];
return ;
}
int mid=(l+r)>>1;
build(l,mid,cnt<<1);
build(mid+1,r,cnt<<1|1);
pushup(cnt);
}
void change(int l,int r,ll val,int cnt)
{
if(l<=t[cnt].l&&t[cnt].r<=r)
{
t[cnt].sum+=(t[cnt].r-t[cnt].l+1)*val;
t[cnt].laz+=val;
return ;
}
pushdown(cnt);
if(l<=t[cnt<<1].r) change(l,r,val,cnt<<1);
if(r>=t[cnt<<1|1].l) change(l,r,val,cnt<<1|1);
pushup(cnt);
}
ll ask(int l,int r,int cnt)
{
if(l<=t[cnt].l&&t[cnt].r<=r)
{
return t[cnt].sum;
}
pushdown(cnt);
ll ans=0;
if(l<=t[cnt<<1].r) ans+=ask(l,r,cnt<<1);
if(r>=t[cnt<<1|1].l) ans+=ask(l,r,cnt<<1|1);
return ans;
}
ll ask_road(int x,int y)
{
ll ans=0;
while(top[x]!=top[y])
{
if(d[top[x]]<d[top[y]])
swap(x,y);
ans+=ask(id[top[x]],id[x],1);
x=f[top[x]];
}
if(id[x]>id[y]) swap(x,y);
ans+=ask(id[x],id[y],1);
return ans;
}
int main(void)
{
scanf("%d%d",&n,&q);
for(int i=1;i<=n;i++)
{
scanf("%d",&vi[i]);
}
int pos,x,y,z;
for(int i=1;i<n;i++)
{
scanf("%d%d",&x,&y);
add(x,y);
add(y,x);
}
dfs1(1,0);
dfs2(1,1);
build(1,cnt,1);
for(int i=1;i<=q;i++)
{
scanf("%d",&pos);
if(pos==1)
{
scanf("%d%d",&x,&z);
change(id[x],id[x],z,1);
}
else if(pos==2)
{
scanf("%d%d",&x,&z);
change(id[x],id[x]+si[x]-1,z,1);
}
else
{
scanf("%d",&x);
printf("%lld\n",ask_road(1,x));
}
}
return 0;
}
六、P4116 Qtree3：
题目描述
给出N个点的一棵树（N-1条边），节点有白有黑，初始全为白
有两种操作：
0 i : 改变某点的颜色（原来是黑的变白，原来是白的变黑）
1 v : 询问1到v的路径上的第一个黑点，若无，输出-1
输入格式
第一行 N，Q，表示N个点和Q个操作
第二行到第N行N-1条无向边
再之后Q行，每行一个操作"0 i" 或者"1 v" (1 ≤ i, v ≤ N).
输出格式
对每个1 v操作输出结果
输入输出样例
输入 #1 复制
9 8
1 2
1 3
2 4
2 9
5 9
7 9
8 9
6 8
1 3
0 8
1 6
1 7
0 2
1 9
0 2
1 9
输出 #1 复制
-1
8
-1
2
-1
说明/提示
For 1/3 of the test cases, N=5000, Q=400000.
For 1/3 of the test cases, N=10000, Q=300000.
For 1/3 of the test cases, N=100000, Q=100000.
用个set维护一下每条重链的黑色点就好了，标号小的靠前。
然后就可以跳来跳去了。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#include<set>
#include<vector>
#define ll long long
#define llu unsigned ll
using namespace std;
const ll lnf=0x3f3f3f3f3f3f3f3f;
const int inf=0x3f3f3f3f;
const int maxn=100100;
int n,q;
char str[20];
int head[maxn],ver[maxn<<1],nt[maxn<<1];
int f[maxn],d[maxn],si[maxn],son[maxn];
int id[maxn],top[maxn],rk[maxn];
int vi[maxn];
int tot=1,cnt=0;
set<int>se[maxn];
void add(int x,int y)
{
ver[++tot]=y,nt[tot]=head[x],head[x]=tot;
}
void dfs1(int x,int fa)
{
int max_son=0;
si[x]=1;
for(int i=head[x];i;i=nt[i])
{
int y=ver[i];
if(y==fa) continue;
d[y]=d[x]+1;
f[y]=x;
dfs1(y,x);
si[x]+=si[y];
if(si[y]>max_son) max_son=si[y],son[x]=y;
}
}
void dfs2(int x,int t)
{
top[x]=t;
id[x]=++cnt;
rk[cnt]=x;
if(!son[x]) return ;
dfs2(son[x],t);
for(int i=head[x];i;i=nt[i])
{
int y=ver[i];
if(y!=son[x]&&y!=f[x])
dfs2(y,y);
}
}
int main(void)
{
scanf("%d%d",&n,&q);
int pos,x,y,z;
for(int i=1;i<n;i++)
{
scanf("%d%d",&x,&y);
add(x,y);
add(y,x);
}
dfs1(1,0);
dfs2(1,1);
for(int i=1;i<=q;i++)
{
scanf("%d%d",&pos,&x);
if(pos==0)
{
vi[x]^=1;
if(vi[x]==1) se[top[x]].insert(id[x]);
else se[top[x]].erase(id[x]);
}
else if(pos==1)
{
int ans=inf;
while(x)
{
int k=*se[top[x]].begin();
if(se[top[x]].size())
if(d[rk[k]]<=d[x]) ans=rk[k];
x=f[top[x]];
}
printf("%d\n",ans==inf?-1:ans);
}
}
return 0;
}
七、P4092 [HEOI2016/TJOI2016]树：
题目描述
在 2016 年，佳媛姐姐刚刚学习了树，非常开心。现在他想解决这样一个问题：给定一颗有根树，根为 11 ，有以下两种操作：
标记操作：对某个结点打上标记。（在最开始，只有结点 11 有标记，其他结点均无标记，而且对于某个结点，可以打多次标记。）
询问操作：询问某个结点最近的一个打了标记的祖先。（这个结点本身也算自己的祖先）
你能帮帮她吗?
输入格式
第一行两个正整数 NN 和 QQ 分别表示节点个数和操作次数。
接下来 N-1N−1 行，每行两个正整数 u,v ,, (1 \leqslant u,v \leqslant n)u,v(1⩽u,v⩽n) 表示 uu 到 vv 有一条有向边。
接下来 QQ 行，形如 oper num ，oper 为 C 时表示这是一个标记操作, oper 为 Q 时表示这是一个询问操作。
输出格式
输出一个正整数，表示结果
输入输出样例
输入 #1 复制
5 5
1 2
1 3
2 4
2 5
Q 2
C 2
Q 2
Q 5
Q 3
输出 #1 复制
1
2
2
1
说明/提示
30%30% 的数据，1 \leqslant N, Q \leqslant 10001⩽N,Q⩽1000 ；
70%70% 的数据，1 \leqslant N, Q \leqslant 100001⩽N,Q⩽10000 ；
100%100% 的数据，1 \leqslant N, Q \leqslant 1000001⩽N,Q⩽100000 。
这题本来也想用set跳来跳去，可是总是t，氧气，臭氧优化都没用。
就写了线段树，可是应该都是nlogn logn
//后来查阅资料发现
//lower_bound(set.begin(),set.end(),val)
//upper_bound(set.begin(),set.end(),val)
//都是O（n）的，
//set的nlogn 应该这样写：
//set.lower_bound(val);
//set.upper_bound(val);
//其中上文中的set都是指set类型的对象。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#include<set>
#include<vector>
#define ll long long
#define llu unsigned ll
using namespace std;
char buffer[100001],*S,*T;
inline char Get_Char()
{
if (S==T)
{
T=(S=buffer)+fread(buffer,1,100001,stdin);
if (S==T) return EOF;
}
return *S++;
}
inline int read()
{
char c;int re=0;
for(c=Get_Char();c<'0'||c>'9';c=Get_Char());
while(c>='0'&&c<='9') re=(re<<1)+(re<<3)+(c-'0'),c=Get_Char();
return re;
}
inline char read_char()
{
char c;
for(c=Get_Char();c<'A'||c>'Z';c=Get_Char());
return c;
}
const ll lnf=0x3f3f3f3f3f3f3f3f;
const int inf=0x3f3f3f3f;
const int maxn=100100;
int n,q;
char str[20];
int head[maxn],ver[maxn<<1],nt[maxn<<1];
int f[maxn],d[maxn],si[maxn],son[maxn];
int id[maxn],top[maxn],rk[maxn];
int vi[maxn];
int tot=1,cnt=0;
void add(int x,int y)
{
ver[++tot]=y,nt[tot]=head[x],head[x]=tot;
}
void dfs1(int x,int fa)
{
int max_son=0;
si[x]=1;
for(int i=head[x];i;i=nt[i])
{
int y=ver[i];
if(y==fa) continue;
d[y]=d[x]+1;
f[y]=x;
dfs1(y,x);
si[x]+=si[y];
if(si[y]>max_son) max_son=si[y],son[x]=y;
}
}
void dfs2(int x,int t)
{
top[x]=t;
id[x]=++cnt;
rk[cnt]=x;
if(!son[x]) return ;
dfs2(son[x],t);
for(int i=head[x];i;i=nt[i])
{
int y=ver[i];
if(y!=son[x]&&y!=f[x])
dfs2(y,y);
}
}
struct node
{
int l,r;
int maxx;
}t[maxn<<2];
void pushup(int cnt)
{
t[cnt].maxx=max(t[cnt<<1].maxx,t[cnt<<1|1].maxx);
}
void build(int l,int r,int cnt)
{
t[cnt].l=l,t[cnt].r=r;
t[cnt].maxx=-1;
if(l==r) return ;
int mid=(l+r)>>1;
build(l,mid,cnt<<1);
build(mid+1,r,cnt<<1|1);
pushup(cnt);
}
void change(int pos,int cnt)
{
if(t[cnt].l==t[cnt].r)
{
t[cnt].maxx=t[cnt].l;
return ;
}
if(pos<=t[cnt<<1].r) change(pos,cnt<<1);
else change(pos,cnt<<1|1);
pushup(cnt);
}
int ask(int l,int r,int cnt)
{
if(l<=t[cnt].l&&t[cnt].r<=r)
{
return t[cnt].maxx;
}
int ans=-inf;
if(l<=t[cnt<<1].r) ans=max(ans,ask(l,r,cnt<<1));
if(r>=t[cnt<<1|1].l) ans=max(ans,ask(l,r,cnt<<1|1));
return ans;
}
int ask_road(int x,int y)
{
int ans=-1;
while(top[x]!=top[y])
{
if(d[top[x]]<d[top[y]]) swap(x,y);
ans=ask(id[top[x]],id[x],1);
if(ans!=-1) return rk[ans];
x=f[top[x]];
}
if(id[x]>id[y]) swap(x,y);
ans=ask(id[x],id[y],1);
return rk[ans];
}
int main(void)
{
scanf("%d%d",&n,&q);
int x,y,z;
char pos[20];
for(int i=1;i<n;i++)
{
scanf("%d%d",&x,&y);
add(x,y);
add(y,x);
}
dfs1(1,0);
dfs2(1,1);
build(1,cnt,1);
change(id[1],1);
for(int i=1;i<=q;i++)
{
scanf("%s%d",pos,&x);
if(pos[0]=='Q')
{
printf("%d\n",ask_road(1,x));
}
else change(id[x],1);
}
return 0;
}
八、P2486 [SDOI2011]染***r>
输出格式
对于每个询问操作，输出一行答案。
输入输出样例
输入 #1 复制
6 5
2 2 1 2 1 1
1 2
1 3
2 4
2 5
2 6
Q 3 5
C 2 1 1
Q 3 5
C 5 1 2
Q 3 5
输出 #1 复制
3
1
2
维护区间颜色种类数，区间左端点颜***间右端点颜色。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#include<set>
#include<vector>
#define ll long long
#define llu unsigned ll
using namespace std;
char buffer[100001],*S,*T;
inline char Get_Char()
{
if (S==T)
{
T=(S=buffer)+fread(buffer,1,100001,stdin);
if (S==T) return EOF;
}
return *S++;
}
inline int read()
{
char c;int re=0;
for(c=Get_Char();c<'0'||c>'9';c=Get_Char());
while(c>='0'&&c<='9') re=(re<<1)+(re<<3)+(c-'0'),c=Get_Char();
return re;
}
inline char read_char()
{
char c;
for(c=Get_Char();c<'A'||c>'Z';c=Get_Char());
return c;
}
const ll lnf=0x3f3f3f3f3f3f3f3f;
const int inf=0x3f3f3f3f;
const int maxn=100100;
int n,q;
char str[20];
int head[maxn],ver[maxn<<1],nt[maxn<<1];
int f[maxn],d[maxn],si[maxn],son[maxn];
int id[maxn],top[maxn],rk[maxn];
int vi[maxn];
int tot=1,cnt=0;
void add(int x,int y)
{
ver[++tot]=y,nt[tot]=head[x],head[x]=tot;
}
void dfs1(int x,int fa)
{
int max_son=0;
si[x]=1;
for(int i=head[x];i;i=nt[i])
{
int y=ver[i];
if(y==fa) continue;
d[y]=d[x]+1;
f[y]=x;
dfs1(y,x);
si[x]+=si[y];
if(si[y]>max_son) max_son=si[y],son[x]=y;
}
}
void dfs2(int x,int t)
{
top[x]=t;
id[x]=++cnt;
rk[cnt]=x;
if(!son[x]) return ;
dfs2(son[x],t);
for(int i=head[x];i;i=nt[i])
{
int y=ver[i];
if(y!=son[x]&&y!=f[x])
dfs2(y,y);
}
}
struct node
{
int l,r;
int lcolor,rcolor;
int laz;
int sum;
}t[maxn<<2];
void pushup(int cnt)
{
t[cnt].lcolor=t[cnt<<1].lcolor;
t[cnt].rcolor=t[cnt<<1|1].rcolor;
int ans=t[cnt<<1].sum+t[cnt<<1|1].sum;
if(t[cnt<<1].rcolor==t[cnt<<1|1].lcolor)
ans--;
t[cnt].sum=ans;
}
void pushdown(int cnt)
{
if(t[cnt].laz)
{
t[cnt<<1].laz=t[cnt<<1|1].laz=t[cnt].laz;
t[cnt<<1].sum=t[cnt<<1|1].sum=1;
t[cnt<<1].lcolor=t[cnt<<1].rcolor=t[cnt].laz;
t[cnt<<1|1].lcolor=t[cnt<<1|1].rcolor=t[cnt].laz;
t[cnt].laz=0;
}
}
void build(int l,int r,int cnt)
{
t[cnt].l=l,t[cnt].r=r;
t[cnt].sum=0;
t[cnt].laz=0;
if(l==r)
{
t[cnt].sum=1;
t[cnt].lcolor=t[cnt].rcolor=vi[rk[l]];
return ;
}
int mid=(l+r)>>1;
build(l,mid,cnt<<1);
build(mid+1,r,cnt<<1|1);
pushup(cnt);
}
void change(int l,int r,int val,int cnt)
{
if(l<=t[cnt].l&&t[cnt].r<=r)
{
t[cnt].sum=1;
t[cnt].lcolor=t[cnt].rcolor=val;
t[cnt].laz=val;
return ;
}
pushdown(cnt);
if(l<=t[cnt<<1].r) change(l,r,val,cnt<<1);
if(r>=t[cnt<<1|1].l) change(l,r,val,cnt<<1|1);
pushup(cnt);
}
node ask(int l,int r,int cnt)
{
if(l<=t[cnt].l&&t[cnt].r<=r)
{
return t[cnt];
}
pushdown(cnt);
if(l>=t[cnt<<1|1].l) return ask(l,r,cnt<<1|1);
else if(r<=t[cnt<<1].r) return ask(l,r,cnt<<1);
else
{
node a,b,c;
a=ask(l,r,cnt<<1);
b=ask(l,r,cnt<<1|1);
c.lcolor=a.lcolor;
c.rcolor=b.rcolor;
int ans=a.sum+b.sum;
if(a.rcolor==b.lcolor)
ans--;
c.sum=ans;
return c;
}
}
void change_road(int x,int y,int val)
{
while(top[x]!=top[y])
{
if(d[top[x]]<d[top[y]])
swap(x,y);
change(id[top[x]],id[x],val,1);
x=f[top[x]];
}
if(id[x]>id[y]) swap(x,y);
change(id[x],id[y],val,1);
}
int ask_road(int x,int y)
{
int ans=0;
node ans1,ans2,res;
ans1.lcolor=-1,ans2.lcolor=-1;
while(top[x]!=top[y])
{
if(d[top[x]]<d[top[y]])
swap(x,y),swap(ans1,ans2);
res=ask(id[top[x]],id[x],1);
ans+=res.sum;
if(ans1.lcolor==res.rcolor)
ans--;
ans1=res;
x=f[top[x]];
}
if(id[x]>id[y]) swap(x,y),swap(ans1,ans2);
res=ask(id[x],id[y],1);
ans+=res.sum;
if(res.lcolor==ans1.lcolor)
ans--;
if(res.rcolor==ans2.lcolor)
ans--;
return ans;
}
int main(void)
{
scanf("%d%d",&n,&q);
for(int i=1;i<=n;i++)
{
scanf("%d",&vi[i]);
}
int x,y,z;
char pos[20];
for(int i=1;i<n;i++)
{
scanf("%d%d",&x,&y);
add(x,y);
add(y,x);
}
dfs1(1,0);
dfs2(1,1);
build(1,cnt,1);
for(int i=1;i<=q;i++)
{
scanf("%s",pos);
if(pos[0]=='Q')
{
scanf("%d%d",&x,&y);
printf("%d\n",ask_road(x,y));
}
else
{
scanf("%d%d%d",&x,&y,&z);
change_road(x,y,z);
}
}
return 0;
}
京公网安备 11010502036488号