打了快一星期的qtree终于打完了- - （其实还有两题改不出来弃疗了QAQ）
orz神AK一星期前就虐完QTREE
避免忘记还是简单写下题解吧0 0
题意：
给出一颗带边权树
一个操作：修改边权
还有一个询问：求x到y路径上边权最大值
树链剖分模版题- -blabla
代码：
#include <cstdio>
#include <cstring>
const int N=;
struct inli{
int next,data,lon;
inli(const int a=,const int b=,const int c=):
next(a),data(b),lon(c){}
}line[N*];
struct info{
int x,y;
info(const int a=,const int b=):
x(a),y(b){}
}sline[N];
int n,t,nl,dfss,back[N],tree[N*],deep[N],num[N],hard[N],dfn[N],fl[N],fat[N],gr[N],son[N];
int st,si;
char s[];
int max(int x,int y){ return x>y ? x : y; }
void swap(int &x,int &y){ int t=x; x=y,y=t; }
void clean(){
nl=dfss=;
memset(son,,sizeof(son));
memset(hard,,sizeof(hard));
memset(tree,,sizeof(tree));
}
void makehard(int t){
num[t]=;
for (int i=son[t];i;i=line[i].next)
if (line[i].data!=fat[t]){
int ne=line[i].data;
fat[ne]=t;
deep[ne]=deep[t]+;
fl[ne]=line[i].lon;
makehard(ne);
num[t]+=num[ne];
if (num[hard[t]]<num[ne]) hard[t]=ne;
}
}
void dfs(int t,int gra){
dfn[t]=++dfss;
back[dfss]=t;
gr[t]=gra;
if (hard[t]) dfs(hard[t],gra);
for (int i=son[t];i;i=line[i].next){
int ne=line[i].data;
if (ne!=fat[t] && ne!=hard[t]) dfs(ne,ne);
}
}
void build(int l,int r,int rt){
if (l==r-){
tree[rt]=fl[back[r]];
return;
}
int mid=(l+r)/;
build(l,mid,rt*);
build(mid,r,rt*+);
tree[rt]=max(tree[rt*],tree[rt*+]);
}
int getmax(int l,int r,int rt,int x,int y){
if (x==y) return ;
if (x<=l && r<=y) return tree[rt];
int mid=(l+r)/,res=;
if (x<mid) res=max(res,getmax(l,mid,rt*,x,y));
if (mid<y) res=max(res,getmax(mid,r,rt*+,x,y));
return res;
}
int getans(int x,int y){
if (x==y) return ;
if (gr[x]==gr[y]){
if (deep[x]>deep[y]) swap(x,y);
return getmax(,n,,dfn[x],dfn[y]);
}
if (deep[gr[x]]<deep[gr[y]]) swap(x,y);
return max(getans(fat[gr[x]],y),max(getmax(,n,,dfn[gr[x]],dfn[x]),fl[gr[x]]));
}
void change2(int l,int r,int rt,int x,int y){
if (l+==r) return (void)(tree[rt]=y);
int mid=(l+r)/;
if (x<mid) change2(l,mid,rt*,x,y);
else change2(mid,r,rt*+,x,y);
tree[rt]=max(tree[rt*],tree[rt*+]);
}
void change(int t,int s){
int x=sline[t].x,y=sline[t].y;
if (deep[x]>deep[y]) swap(x,y);
if (gr[x]==gr[y]) change2(,n,,dfn[x],s);
else fl[y]=s;
}
int main(){
freopen("spoj375.in","r",stdin);
freopen("spoj375.out","w",stdout);
for (scanf("%d",&t);t;t--){
clean();
scanf("%d\n",&n);
int x,y,z;
for (int i=;i<n;i++){
scanf("%d%d%d\n",&x,&y,&z);
line[++nl]=inli(son[x],y,z),son[x]=nl;
line[++nl]=inli(son[y],x,z),son[y]=nl;
sline[i]=info(x,y);
}
makehard();
dfs(,);
build(,n,);
int i=;
while (){
si=++i;
st=t;
if (i==)
i=;
if (t==)
t=;
if (t== && i==)
t=;
scanf("%s",s);
if (s[]=='Q'){
scanf("%d%d\n",&x,&y);
printf("%d\n",getans(x,y));
}
if (s[]=='C'){
scanf("%d%d\n",&x,&y);
change(x,y);
}
if (s[]=='D') break;
if (n==)
n=;
}
}
fclose(stdin);
fclose(stdout);
}
题意：
给出一颗带边权树 两个询问
1.求x到y路径上边权和
2.求x到y路径上的第k条边的边权
边权和还是树链剖分模版- -
求第k条边 刚想了一下貌似树剖也能做 但是我是用倍增的
代码：
#include <cstdio>
#include <cstring>
const int N=;
struct inli{
int next,data,lon;
inli(const int a=,const int b=,const int c=):
next(a),data(b),lon(c){}
}line[N*];
int t,n,nl,deep[N],son[N],fat[N][],dis[N][];
char s[];
void swap(int &x,int &y){ int t=x; x=y,y=t; }
void clean(){
nl=;
for (int i=;i<=n;i++){
son[i]=;
memset(fat[i],,sizeof(fat[i]));
}
}
void makefat(int t){
for (int i=;fat[fat[t][i-]][i-];++i){
fat[t][i]=fat[fat[t][i-]][i-];
dis[t][i]=dis[t][i-]+dis[fat[t][i-]][i-];
}
for (int i=son[t];i;i=line[i].next)
if (line[i].data!=fat[t][]){
int ne=line[i].data;
deep[ne]=deep[t]+;
fat[ne][]=t;
dis[ne][]=line[i].lon;
makefat(ne);
}
}
int getdis(int x,int y){
if (x==y) return ;
if (deep[x]!=deep[y]){
if (deep[x]<deep[y]) swap(x,y);
int i=;
for (;deep[fat[x][i]]>=deep[y] && fat[x][i];++i);
--i;
return dis[x][i]+getdis(fat[x][i],y);
}
if (fat[x][]==fat[y][]) return dis[x][]+dis[y][];
int i=;
for (;fat[x][i]!=fat[y][i] && fat[x][i];++i);
--i;
return dis[x][i]+dis[y][i]+getdis(fat[x][i],fat[y][i]);
}
int getgr(int x,int y){
if (x==y) return x;
if (deep[x]!=deep[y]){
if (deep[x]<deep[y]) swap(x,y);
int i=;
for (;deep[fat[x][i]]>=deep[y] && fat[x][i];++i);
--i;
return getgr(fat[x][i],y);
}
if (fat[x][]==fat[y][]) return fat[x][];
int i=;
for (;fat[x][i]!=fat[y][i] && fat[x][i];++i);
--i;
return getgr(fat[x][i],fat[y][i]);
}
int getans(int t,int s){
if (s==) return t;
int i=;
for (;deep[t]-deep[fat[t][i]]+<=s && fat[t][i];++i);
--i;
return getans(fat[t][i],s-(deep[t]-deep[fat[t][i]]));
}
int main(){
freopen("spoj913.in","r",stdin);
freopen("spoj913.out","w",stdout);
for (scanf("%d",&t);t;t--){
scanf("%d\n",&n);
clean();
int x,y,z;
for (int i=;i<n;i++){
scanf("%d%d%d\n",&x,&y,&z);
line[++nl]=inli(son[x],y,z),son[x]=nl;
line[++nl]=inli(son[y],x,z),son[y]=nl;
}
makefat();
while (){
scanf("%s",s);
if (s[]=='I'){
scanf("%d%d\n",&x,&y);
printf("%d\n",getdis(x,y));
}
if (s[]=='K'){
scanf("%d%d%d\n",&x,&y,&z);
int gr=getgr(x,y);
if (deep[x]-deep[gr]+<z){
swap(x,y);
z=deep[x]+deep[y]-deep[gr]*+-z;
}
printf("%d\n",getans(x,z));
}
if (s[]=='O') break;
}
puts("");
}
fclose(stdin);
fclose(stdout);
}
题意：
给出一颗点初始全白的树
一个操作：修改点的颜色
一个询问：求1到点x的最近黑点 没有则输出-1
这题我觉得能用动态树做
询问的时候把x access到根 splay上维护深度最小的黑点
树链剖分也可以做 线段树维护最前面的黑点即可（貌似比较简单- -）
这题我貌似就yy了一下没打- -
题意：
给出一颗点初始全白的带边权树
一个操作：修改点的颜色
一个询问：求最远的两个白色点的距离
QAQ这题被spoj卡时了啊 根本调不出来- -
其实这题好像是去湖南培训的一道题的弱化版- - 我竟然没想出来orz
我的做法是点分治+3*堆
我们定义某重心的子树的重心是 该重心的重儿子 反之重父亲
维护第一个堆que1维护 该点管辖范围内的点到该点重父亲的距离最大值
第二个堆que2维护 该点的每个重儿子的que1的堆顶的最大值（如果该点为白点 要插入一个dis为0的值）
每个que2的前2大的距离和即为两白点经过该点答案
第三个堆ans3就维护所有的que2的前2大的距离和的最大值
因为我用的是priority_queue 所以不支持删除- - 于是我就每个对打了一个时间戳
一修改3个堆一个套一个全部要改 整个世界格局混乱orz 思路不清晰就很容易晕
这题我打了3天啊QAQ（最后还没调出来←_←）
这题没A就不贴代码了- -
题意：
给出一颗点初始全白的带边权树
一个操作：修改点的颜色
一个询问：求离点x最远的白点的距离
这题和上题做法差不多 枚举管辖范围包括x的重心即可
因为上一题被卡时了 - - 这题也不敢打orz
题意：
给出一颗点初始全白的树
一个操作：修改点的颜色
一个询问：求点x与多少点相连 两点相连条是这两点的路径上的点都与点x的颜色相同
这题我是用树链剖分做的
维护f[2][i]表示i点为黑色或白色时 i的子树中与i相连的点的个数
那么x点的答案就是x点的最浅相连祖先的f[col[x]]值
当修改某点的颜色时 就修改该点到最浅相连祖先的父亲的f值即可
这题也可以用动态树做
详见QTREE7- - 233为什么和神ak写的一样
代码：
#include <cstdio>
const int N=;
struct inli{
int next,data;
inli(const int a=,const int b=):
next(a),data(b){}
}line[N*];
int n,m,nl,dfss,deep[N],gr[N],hard[N],num[N],back[N],dfn[N],son[N],tree[][N*],fat[N][],coltree[N*],col[N];
void makehard(int t){
for (int i=;fat[fat[t][i-]][i-];++i) fat[t][i]=fat[fat[t][i-]][i-];
num[t]=;
for (int i=son[t];i;i=line[i].next)
if (line[i].data!=fat[t][]){
int ne=line[i].data;
fat[ne][]=t;
deep[ne]=deep[t]+;
makehard(ne);
num[t]+=num[ne];
if (num[ne]>num[hard[t]]) hard[t]=ne;
}
}
void dfs(int t,int gra){
gr[t]=gra;
dfn[t]=++dfss;
back[dfss]=t;
if (hard[t]) dfs(hard[t],gra);
for (int i=son[t];i;i=line[i].next){
int ne=line[i].data;
if (ne!=fat[t][] && ne!=hard[t]) dfs(ne,ne);
}
} void pushdown(int t){
tree[][t*]+=tree[][t];
tree[][t*+]+=tree[][t];
tree[][t]=;
tree[][t*]+=tree[][t];
tree[][t*+]+=tree[][t];
tree[][t]=;
}
void build(int l,int r,int rt){
if (l==r){
tree[][rt]=num[back[l]];
tree[][rt]=;
return;
}
int mid=(l+r)/;
build(l,mid,rt*);
build(mid+,r,rt*+);
}
int getgr(int l,int r,int rt,int x,int y,int z){
int mid=(l+r)/,res;
if (x<=l && r<=y){
if (coltree[rt]==z) return l;
if (l==r) return -;
if (coltree[rt*+]!=z) return getgr(mid+,r,rt*+,x,y,z);
res=getgr(l,mid,rt*,x,y,z);
return res==- ? mid+ : res;
}
if (y<=mid) return getgr(l,mid,rt*,x,y,z);
if (x>mid) return getgr(mid+,r,rt*+,x,y,z);
res=getgr(mid+,r,rt*+,x,y,z);
if (res==-) return -;
if (res>mid+) return res;
res=getgr(l,mid,rt*,x,y,z);
return res==- ? mid+ : res;
}
int getans(int l,int r,int rt,int x,int y){
if (l==r) return tree[y][rt];
int mid=(l+r)/;
pushdown(rt);
if (x<=mid) return getans(l,mid,rt*,x,y);
else return getans(mid+,r,rt*+,x,y);
}
void addtree(int l,int r,int rt,int x,int y,int z,int co){
if (x<=l && r<=y) return (void)(tree[co][rt]+=z);
int mid=(l+r)/;
pushdown(rt);
if (x<=mid) addtree(l,mid,rt*,x,y,z,co);
if (mid<y) addtree(mid+,r,rt*+,x,y,z,co);
}
void changecol(int l,int r,int rt,int x){
if (l==r) return (void)(coltree[rt]^=);
int mid=(l+r)/;
if (x<=mid) changecol(l,mid,rt*,x);
else changecol(mid+,r,rt*+,x);
coltree[rt]=coltree[rt*]==coltree[rt*+] ? coltree[rt*] : -;
} int getfat(int t,int co){
if (!fat[t][] || col[fat[t][]]!=co) return t;
int save=back[getgr(,n,,dfn[gr[t]],dfn[t],co)];
if (save!=gr[t] || !fat[gr[t]][] || col[fat[gr[t]][]]!=co) return save;
else return getfat(fat[gr[t]][],co);
}
void add(int co,int x,int y,int s){
if (deep[x]>deep[y]) return;
if (gr[x]==gr[y]){
addtree(,n,,dfn[x],dfn[y],s,co);
return;
}
addtree(,n,,dfn[gr[y]],dfn[y],s,co);
add(co,x,fat[gr[y]][],s);
}
void change(int t){
int p1=getans(,n,,dfn[t],col[t]),p2=getans(,n,,dfn[t],col[t]^);
/*if (fat[t][0]){
if (col[fat[t][0]]==col[t]) add(col[t]^1,fat[t][0],fat[t][0],p2);
else add(col[t],fat[t][0],fat[t][0],-p1);
}*/
int fa=getfat(t,col[t]);
if (fat[fa][]) fa=fat[fa][];
add(col[t],fa,fat[t][],-p1);
col[t]^=;
changecol(,n,,dfn[t]);
fa=getfat(t,col[t]);
if (fat[fa][]) fa=fat[fa][];
add(col[t],fa,fat[t][],p2);
}
int main(){
freopen("spoj16549.in","r",stdin);
freopen("spoj16549.out","w",stdout);
scanf("%d",&n);
for (int x,y,i=;i<n;i++){
scanf("%d%d",&x,&y);
line[++nl]=inli(son[x],y),son[x]=nl;
line[++nl]=inli(son[y],x),son[y]=nl;
}
deep[]=;
makehard();
dfs(,);
build(,n,);
scanf("%d",&m);
for (int x,y,i=;i<=m;i++){
scanf("%d%d",&x,&y);
if (i==)
i=;
if (x) change(y);
else printf("%d\n",getans(,n,,dfn[getfat(y,col[y])],col[y]));
}
fclose(stdin);
fclose(stdout);
}
题意：
给出一颗点为黑色或白色的带点权的树
两个操作：
1.修改点的颜色
2.修改点权
一个询问：
求点与x相连的点的最大点权 两点相连条是这两点的路径上的点都与点x的颜色相同
把黑点和白点建成两颗树 同色的相连点就在同一颗树上
用set维护某点的轻边子树的最大值（取每个轻边子树的最大点权存进set）
再用动态树splay维护重边上的点最大值
询问时把该点access到根 再splay求出答案即可
access的时候要注意 当修改重边时 set要删除原轻边的最大值 加上原重边的最大值
修改点权也很好处理 - -稍微想想就知道了
修改颜色 则需要从某颜色的树上cut下一个点 再在另外颜色的树上link上一个点
但是当图为菊花图时link上的点的轻边个数可能有O(n)个 在set上一个个插入 一次操作就需要O(nlogn) 显然tle
orz神ak想到一种特别好的方法
在黑数上如果某点有个儿子的颜色为黑色就保留该点 白树同理 这样每次修改在set上就只会插入或删除一个点 就能过了
代码：
#include <cstdio>
#include <set>
using namespace std;
const int N=;
struct intr{
int fat,lc,rc,t,max,root;
intr(const int a=,const int b=,const int c=,const int d=,const int e=,const int f=):
fat(a),lc(b),rc(c),t(d),max(e),root(f){}
};
struct inli{
int next,data;
inli(const int a=,const int b=):
next(a),data(b){}
}line[N*];
int n,m,nl,son[N],col[N],fat[N];
int max(int x,int y){ return x>y ? x : y; }
struct LCT{
intr tree[N];
int xx;
multiset <int> se[N];
void clean(){ tree[]=intr(); }
void maintain(int t){
tree[t].max=tree[t].t;
if (se[t].size()) tree[t].max=max(tree[t].max,*se[t].rbegin());
if (tree[t].lc) tree[t].max=max(tree[t].max,tree[tree[t].lc].max);
if (tree[t].rc) tree[t].max=max(tree[t].max,tree[tree[t].rc].max);
}
void left(int t){
int fa=tree[t].fat,r=tree[t].rc;
tree[t].rc=tree[r].lc,tree[tree[r].lc].fat=t;
tree[r].lc=t,tree[t].fat=r;
if (tree[t].root) tree[t].root=,tree[r].root=;
else if (tree[fa].lc==t) tree[fa].lc=r;
else tree[fa].rc=r;
tree[r].fat=fa;
clean();
maintain(t);
maintain(r);
}
void right(int t){
int fa=tree[t].fat,l=tree[t].lc;
tree[t].lc=tree[l].rc,tree[tree[l].rc].fat=t;
tree[l].rc=t,tree[t].fat=l;
if (tree[t].root) tree[t].root=,tree[l].root=;
else if (tree[fa].lc==t) tree[fa].lc=l;
else tree[fa].rc=l;
tree[l].fat=fa;
clean();
maintain(t);
maintain(l);
}
void splay(int t){
while (!tree[t].root){
int fa=tree[t].fat,gr=tree[fa].fat;
if (tree[fa].root){
if (tree[fa].lc==t) right(fa);
else left(fa);
}else if (tree[gr].lc==fa){
if (tree[fa].lc==t) right(gr),right(fa);
else left(fa),right(gr);
}else if (tree[fa].rc==t) left(gr),left(fa);
else right(fa),left(gr);
}
} void access(int t){
xx=;
for (int x=,y=t;y;x=y,y=tree[y].fat){
//Wa: no(x=y) y=fat[y];
splay(y);
if (x) se[y].erase(tree[x].max);
if (tree[y].rc) se[y].insert(tree[tree[y].rc].max);
tree[x].root=;
tree[tree[y].rc].root=;
// no (tree[tree[y].rc].root=1;)
tree[y].rc=x;
clean();
maintain(y);
}
}
int getl(int t){
while (tree[t].lc) t=tree[t].lc;
return t;
}
int getans(int t){
access(t);
splay(t);
int root=getl(t);
splay(root);
return col[root]==col[t] ? tree[root].max : tree[tree[root].rc].max;
// wa:tree[t].max
}
void changenum(int t,int s){
access(t);
splay(t);
tree[t].t=s;
maintain(t);
}
void cut(int t){
access(t);
splay(t);
tree[tree[t].lc].fat=;
tree[tree[t].lc].root=;
tree[t].lc=;
maintain(t);
}
void link(int x,int y){
splay(x);
access(y);
splay(y);
tree[x].fat=y;
se[y].insert(tree[x].max);
maintain(y);
}
}lct[];
void dfs(int t){
if (fat[t]) lct[col[t]].tree[t].fat=fat[t];
for (int i=son[t];i;i=line[i].next)
if (line[i].data!=fat[t]){
int ne=line[i].data;
fat[ne]=t;
dfs(ne);
lct[col[ne]].se[t].insert(lct[col[ne]].tree[ne].max);
}
lct[].maintain(t);
lct[].maintain(t);
}
void changecol(int t){
if (fat[t]){
lct[col[t]].cut(t);
lct[col[t]^].link(t,fat[t]);
}
col[t]^=;
}
int main(){
freopen("spoj16580.in","r",stdin);
freopen("spoj16580.out","w",stdout);
scanf("%d",&n);
for (int x,y,i=;i<n;i++){
scanf("%d%d",&x,&y);
line[++nl]=inli(son[x],y),son[x]=nl;
line[++nl]=inli(son[y],x),son[y]=nl;
}
for (int i=;i<=n;i++) scanf("%d",&col[i]);
for (int x,i=;i<=n;i++){
scanf("%d",&x);
lct[].tree[i].t=lct[].tree[i].max=x;
lct[].tree[i].t=lct[].tree[i].max=x;
}
dfs();
scanf("%d",&m);
for (int x,y,z,i=;i<=m;i++){
scanf("%d%d",&x,&y);
if (i==)
i=;
if (x==) printf("%d\n",lct[col[y]].getans(y));
if (x==) changecol(y);
if (x==){
scanf("%d",&z);
lct[].changenum(y,z);
lct[].changenum(y,z);
}
}
fclose(stdin);
fclose(stdout);
}