P2146 [NOI2015]软件包管理器
#include<bits/stdc++.h>
using namespace std
;
const int N
=1e5+100;
int head
[N
],ver
[N
<<1],edge
[N
<<1],nex
[N
<<1];
int tot
=0;
void addedge(int x
,int y
,int z
){
ver
[++tot
]=y
,nex
[tot
]=head
[x
];
edge
[tot
]=z
;head
[x
]=tot
;
}
int d
[N
];
int top
[N
];
int dfn
[N
];
int rnk
[N
];
int fa
[N
];
int siz
[N
];
int son
[N
];
int cnt
=0;
#define lc (p<<1)
#define rc (p<<1|1)
#define mid ((t[p].l+t[p].r)>>1)
struct Segment
{
int l
,r
;
int dat
,alz
;
}t
[N
<<2];
void pushup(int p
){
t
[p
].dat
=t
[lc
].dat
+t
[rc
].dat
;
}
void build(int p
,int l
,int r
){
t
[p
].l
=l
,t
[p
].r
=r
;
t
[p
].alz
=0;
if(l
==r
){
t
[p
].dat
=0;
return;
}
build(lc
,l
,mid
);
build(rc
,mid
+1,r
);
pushup(p
);
}
void spread(int p
){
if(t
[p
].alz
!=-1){
t
[lc
].dat
=(t
[lc
].r
-t
[lc
].l
+1)*t
[p
].alz
;
t
[rc
].dat
=(t
[rc
].r
-t
[rc
].l
+1)*t
[p
].alz
;
t
[lc
].alz
=t
[rc
].alz
=t
[p
].alz
;
t
[p
].alz
=-1;
}
}
void update(int p
,int l
,int r
,int val
){
if(l
<=t
[p
].l
&&t
[p
].r
<=r
){
t
[p
].dat
=(t
[p
].r
-t
[p
].l
+1)*val
;
t
[p
].alz
=val
;
return;
}
spread(p
);
if(l
<=mid
) update(lc
,l
,r
,val
);
if(r
>mid
) update(rc
,l
,r
,val
);
pushup(p
);
}
int query(int p
,int l
,int r
){
if(l
<=t
[p
].l
&&t
[p
].r
<=r
){
return t
[p
].dat
;
}
spread(p
);
int val
=0;
if(l
<=mid
) val
+=query(lc
,l
,r
);
if(r
>mid
) val
+=query(rc
,l
,r
);
return val
;
}
void dfs1(int x
,int f
){
d
[x
]=d
[f
]+1;
siz
[x
]=1;
fa
[x
]=f
;
int maxson
=-1;
for(int i
=head
[x
];i
;i
=nex
[i
]){
int y
=ver
[i
];
if(y
==f
) continue;
dfs1(y
,x
);
siz
[x
]+=siz
[y
];
if(maxson
<siz
[y
]) maxson
=siz
[y
],son
[x
]=y
;
}
}
void dfs2(int x
,int t
){
top
[x
]=t
;
dfn
[x
]=++cnt
;
rnk
[cnt
]=x
;
if(!son
[x
]) return;
dfs2(son
[x
],t
);
for(int i
=head
[x
];i
;i
=nex
[i
]){
int y
=ver
[i
];
if(y
!=fa
[x
]&&y
!=son
[x
])
dfs2(y
,y
);
}
}
void updRange(int x
,int y
,int val
){
while(top
[x
]!=top
[y
]){
if(d
[top
[x
]]<d
[top
[y
]]) swap(x
,y
);
update(1,dfn
[top
[x
]],dfn
[x
],val
);
x
=fa
[top
[x
]];
}
if(d
[x
]>d
[y
]) swap(x
,y
);
update(1,dfn
[x
],dfn
[y
],val
);
}
int qRange(int x
,int y
){
int ans
=0;
while(top
[x
]!=top
[y
]){
if(d
[top
[x
]]<d
[top
[y
]]) swap(x
,y
);
ans
+=query(1,dfn
[top
[x
]],dfn
[x
]);
x
=fa
[top
[x
]];
}
if(d
[x
]>d
[y
]) swap(x
,y
);
ans
+=query(1,dfn
[x
],dfn
[y
]);
return ans
;
}
int qSon(int x
){
return query(1,dfn
[x
],dfn
[x
]+siz
[x
]-1);
}
void updSon(int x
,int val
){
return update(1,dfn
[x
],dfn
[x
]+siz
[x
]-1,val
);
}
int main(){
int n
;
cin
>>n
;
for(int i
=1;i
<=n
-1;i
++){
int x
;
cin
>>x
;
x
++;
addedge(i
+1,x
,1);
addedge(x
,i
+1,1);
}
dfs1(1,0);
dfs2(1,1);
build(1,1,n
);
int m
;
cin
>>m
;
for(int i
=1;i
<=m
;i
++){
string op
;
int x
;
cin
>>op
>>x
;
x
++;
if(op
=="install"){
int last
=qRange(1,x
);
updRange(1,x
,1);
int now
=qRange(1,x
);
cout
<<now
-last
<<endl
;
}
else{
int last
=qSon(x
);
updSon(x
,0);
int now
=qSon(x
);
cout
<<last
-now
<<endl
;
}
}
return 0;
}
P2590 [ZJOI2008]树的统计
#include<bits/stdc++.h>
using namespace std
;
#define ll long long
const int N
=1e5+100;
const int INF
=0X3F3F3F3F;
int tot
=0;
int head
[N
],ver
[N
<<1],nex
[N
<<1],edge
[N
<<1];
void addedge(int x
,int y
,int z
){
ver
[++tot
]=y
,nex
[tot
]=head
[x
];
edge
[tot
]=z
;head
[x
]=tot
;
}
int d
[N
];
int rnk
[N
];
int top
[N
];
int cnt
=0;
int son
[N
];
int siz
[N
];
int dfn
[N
];
int w
[N
];
int fa
[N
];
#define lc (p<<1)
#define rc (p<<1|1)
#define mid ((t[p].l+t[p].r)>>1)
struct Segment
{
int l
,r
;
ll dat
,mx
;
}t
[N
<<2];
void pushup(int p
){
t
[p
].dat
=t
[lc
].dat
+t
[rc
].dat
;
t
[p
].mx
=max(t
[lc
].mx
,t
[rc
].mx
);
}
void build(int p
,int l
,int r
){
t
[p
].l
=l
,t
[p
].r
=r
;
if(l
==r
){
t
[p
].dat
=t
[p
].mx
=w
[rnk
[l
]];
return;
}
build(lc
,l
,mid
);
build(rc
,mid
+1,r
);
pushup(p
);
}
void update(int p
,int l
,int r
,int val
){
if(l
<=t
[p
].l
&&t
[p
].r
<=r
){
t
[p
].dat
=t
[p
].mx
=val
;
return;
}
if(l
<=mid
) update(lc
,l
,r
,val
);
if(r
>mid
) update(rc
,l
,r
,val
);
pushup(p
);
}
ll
query_sum(int p
,int l
,int r
){
if(l
<=t
[p
].l
&&t
[p
].r
<=r
) {
return t
[p
].dat
;
}
ll val
=0;
if(l
<=mid
) val
=(val
+query_sum(lc
,l
,r
));
if(r
>mid
) val
=(val
+query_sum(rc
,l
,r
));
return val
;
}
ll
query_max(int p
,int l
,int r
){
if(l
<=t
[p
].l
&&t
[p
].r
<=r
){
return t
[p
].mx
;
}
ll val
=-INF
;
if(l
<=mid
) val
=max(val
,query_max(lc
,l
,r
));
if(r
>mid
) val
=max(val
,query_max(rc
,l
,r
));
return val
;
}
void dfs1(int x
,int f
){
d
[x
]=d
[f
]+1;
siz
[x
]=1;
fa
[x
]=f
;
int maxson
=-1;
for(int i
=head
[x
];i
;i
=nex
[i
]){
int y
=ver
[i
];
if(y
==f
) continue;
dfs1(y
,x
);
siz
[x
]+=siz
[y
];
if(siz
[y
]>maxson
) son
[x
]=y
,maxson
=siz
[y
];
}
}
void dfs2(int x
,int t
){
dfn
[x
]=++cnt
;
top
[x
]=t
;
rnk
[cnt
]=x
;
if(!son
[x
]) return;
dfs2(son
[x
],t
);
for(int i
=head
[x
];i
;i
=nex
[i
]){
int y
=ver
[i
];
if(y
!=son
[x
]&&y
!=fa
[x
])
dfs2(y
,y
);
}
}
int qSum(int x
,int y
){
int ans
=0;
while(top
[x
]!=top
[y
]){
if(d
[top
[x
]]<d
[top
[y
]]) swap(x
,y
);
int res
=query_sum(1,dfn
[top
[x
]],dfn
[x
]);
ans
=(ans
+res
);
x
=fa
[top
[x
]];
}
if(d
[x
]>d
[y
]) swap(x
,y
);
int res
=query_sum(1,dfn
[x
],dfn
[y
]);
ans
=(ans
+res
);
return ans
;
}
int qMax(int x
,int y
){
int ans
=-INF
;
while(top
[x
]!=top
[y
]){
if(d
[top
[x
]]<d
[top
[y
]]) swap(x
,y
);
int res
=query_max(1,dfn
[top
[x
]],dfn
[x
]);
ans
=max(ans
,res
);
x
=fa
[top
[x
]];
}
if(d
[x
]>d
[y
]) swap(x
,y
);
int res
=query_max(1,dfn
[x
],dfn
[y
]);
ans
=max(ans
,res
);
return ans
;
}
void updRange(int x
,int val
){
update(1,dfn
[x
],dfn
[x
],val
);
}
int main(){
int n
;
cin
>>n
;
for(int i
=1;i
<=n
-1;i
++){
int x
,y
;
cin
>>x
>>y
;
addedge(x
,y
,1);
addedge(y
,x
,1);
}
for(int i
=1;i
<=n
;i
++) cin
>>w
[i
];
dfs1(1,0);
dfs2(1,1);
build(1,1,n
);
int m
;
cin
>>m
;
for(int i
=1;i
<=m
;i
++){
string op
;
int x
,y
,val
;
cin
>>op
;
if(op
=="QMAX"){
cin
>>x
>>y
;
cout
<<qMax(x
,y
)<<endl
;
}
else if(op
=="QSUM"){
cin
>>x
>>y
;
cout
<<qSum(x
,y
)<<endl
;
}
else{
cin
>>x
>>val
;
updRange(x
,val
);
}
}
return 0;
}
P3038 [USACO11DEC]Grass Planting G
#include<bits/stdc++.h>
using namespace std
;
#define ll long long
const int N
=1e5+100;
int head
[N
],ver
[N
<<1],edge
[N
<<1],nex
[N
<<1];
int tot
=0;
void addedge(int x
,int y
,int z
){
ver
[++tot
]=y
,nex
[tot
]=head
[x
];
edge
[tot
]=z
,head
[x
]=tot
;
}
int d
[N
];
int dfn
[N
];
int fa
[N
];
int siz
[N
];
int son
[N
];
int rnk
[N
];
int top
[N
];
int cnt
=0;
#define lc (p<<1)
#define rc (p<<1|1)
#define mid ((t[p].l+t[p].r)>>1)
#define lc (p<<1)
#define rc (p<<1|1)
#define mid ((t[p].l+t[p].r)>>1)
struct Segment
{
int l
,r
;
ll dat
,alz
;
}t
[N
<<2];
void pushup(int p
){
t
[p
].dat
=t
[lc
].dat
+t
[rc
].dat
;
}
void build(int p
,int l
,int r
){
t
[p
].l
=l
,t
[p
].r
=r
;
t
[p
].alz
=0;
if(l
==r
){
t
[p
].dat
=0;
return;
}
build(lc
,l
,mid
);
build(rc
,mid
+1,r
);
pushup(p
);
}
void spread(int p
){
if(t
[p
].alz
){
t
[lc
].dat
+=(t
[lc
].r
-t
[lc
].l
+1)*t
[p
].alz
;
t
[rc
].dat
+=(t
[rc
].r
-t
[rc
].l
+1)*t
[p
].alz
;
t
[lc
].alz
+=t
[p
].alz
;
t
[rc
].alz
+=t
[p
].alz
;
t
[p
].alz
=0;
}
}
void update(int p
,int l
,int r
,ll val
){
if(l
<=t
[p
].l
&&t
[p
].r
<=r
){
t
[p
].dat
+=(t
[p
].r
-t
[p
].l
+1)*val
;
t
[p
].alz
+=val
;
return;
}
spread(p
);
if(l
<=mid
) update(lc
,l
,r
,val
);
if(r
>mid
) update(rc
,l
,r
,val
);
pushup(p
);
}
ll
query(int p
,int l
,int r
){
if(l
<=t
[p
].l
&&t
[p
].r
<=r
){
return t
[p
].dat
;
}
spread(p
);
ll val
=0;
if(l
<=mid
) val
+=query(lc
,l
,r
);
if(r
>mid
) val
+=query(rc
,l
,r
);
return val
;
}
void updRange(int x
,int y
,ll val
){
while(top
[x
]!=top
[y
]){
if(d
[top
[x
]]<d
[top
[y
]]) swap(x
,y
);
update(1,dfn
[top
[x
]],dfn
[x
],val
);
x
=fa
[top
[x
]];
}
if(d
[x
]>d
[y
]) swap(x
,y
);
update(1,dfn
[x
]+1,dfn
[y
],val
);
}
ll
qRange(int x
,int y
){
ll ans
=0;
while(top
[x
]!=top
[y
]){
if(d
[top
[x
]]<d
[top
[y
]]) swap(x
,y
);
ans
+=query(1,dfn
[top
[x
]],dfn
[x
]);
x
=fa
[top
[x
]];
}
if(d
[x
]>d
[y
]) swap(x
,y
);
ans
+=query(1,dfn
[x
]+1,dfn
[y
]);
return ans
;
}
void dfs1(int x
,int f
){
fa
[x
]=f
;
d
[x
]=d
[f
]+1;
siz
[x
]=1;
int maxson
=-1;
for(int i
=head
[x
];i
;i
=nex
[i
]){
int y
=ver
[i
];
if(y
==f
) continue;
dfs1(y
,x
);
siz
[x
]+=siz
[y
];
if(maxson
<siz
[y
]) maxson
=siz
[y
],son
[x
]=y
;
}
}
void dfs2(int x
,int t
){
top
[x
]=t
;
dfn
[x
]=++cnt
;
rnk
[cnt
]=x
;
if(!son
[x
]) return;
dfs2(son
[x
],t
);
for(int i
=head
[x
];i
;i
=nex
[i
]){
int y
=ver
[i
];
if(y
!=fa
[x
]&&y
!=son
[x
])
dfs2(y
,y
);
}
}
int main(){
int n
,m
;
cin
>>n
>>m
;
for(int i
=1;i
<=n
-1;i
++){
int x
,y
;
cin
>>x
>>y
;
addedge(x
,y
,1);
addedge(y
,x
,1);
}
dfs1(1,0);
dfs2(1,1);
build(1,1,n
);
for(int i
=1;i
<=m
;i
++){
char op
;
int x
,y
;
cin
>>op
>>x
>>y
;
if(op
=='P'){
updRange(x
,y
,1);
}
else{
cout
<<qRange(x
,y
)<<endl
;
}
}
return 0;
}
P3128 [USACO15DEC]Max Flow P
#include<bits/stdc++.h>
using namespace std
;
#define ll long long
const int N
=1e5+100;
int head
[N
],nex
[N
<<1],edge
[N
<<1],ver
[N
<<1];
int tot
=0;
void addedge(int x
,int y
,int z
){
ver
[++tot
]=y
,nex
[tot
]=head
[x
],head
[x
]=tot
;
edge
[tot
]=z
;
}
int d
[N
];
int top
[N
];
int fa
[N
];
int son
[N
];
int siz
[N
];
int cnt
=0;
int dfn
[N
];
int rnk
[N
];
#define lc (p<<1)
#define rc (p<<1|1)
#define mid ((t[p].l+t[p].r)>>1)
struct Segment
{
int l
,r
;
ll dat
,alz
;
}t
[N
<<2];
void pushup(int p
){
t
[p
].dat
=max(t
[lc
].dat
,t
[rc
].dat
);
}
void build(int p
,int l
,int r
){
t
[p
].l
=l
,t
[p
].r
=r
;
t
[p
].alz
=0;
if(l
==r
){
t
[p
].dat
=0;
return;
}
build(lc
,l
,mid
);
build(rc
,mid
+1,r
);
pushup(p
);
}
void spread(int p
){
if(t
[p
].alz
){
t
[lc
].dat
+=t
[p
].alz
;
t
[rc
].dat
+=t
[p
].alz
;
t
[lc
].alz
+=t
[p
].alz
;
t
[rc
].alz
+=t
[p
].alz
;
t
[p
].alz
=0;
}
}
void update(int p
,int l
,int r
,int val
){
if(l
<=t
[p
].l
&&t
[p
].r
<=r
){
t
[p
].dat
+=val
;
t
[p
].alz
+=val
;
return ;
}
spread(p
);
if(l
<=mid
) update(lc
,l
,r
,val
);
if(r
>mid
) update(rc
,l
,r
,val
);
pushup(p
);
}
ll
query(int p
,int l
,int r
){
if(l
<=t
[p
].l
&&t
[p
].r
<=r
) return t
[p
].dat
;
spread(p
);
ll val
=0;
if(l
<=mid
) val
+=query(lc
,l
,r
);
if(r
>mid
) val
+=query(rc
,l
,r
);
return val
;
}
void dfs1(int x
,int f
){
d
[x
]=d
[f
]+1;
fa
[x
]=f
;
siz
[x
]=1;
int maxson
=-1;
for(int i
=head
[x
];i
;i
=nex
[i
]){
int y
=ver
[i
];
if(y
==f
) continue;
dfs1(y
,x
);
siz
[x
]+=siz
[y
];
if(maxson
<siz
[y
]) maxson
=siz
[y
],son
[x
]=y
;
}
}
void dfs2(int x
,int t
){
top
[x
]=t
;
dfn
[x
]=++cnt
;
rnk
[cnt
]=x
;
if(!son
[x
]) return;
dfs2(son
[x
],t
);
for(int i
=head
[x
];i
;i
=nex
[i
]){
int y
=ver
[i
];
if(y
!=fa
[x
]&&y
!=son
[x
])
dfs2(y
,y
);
}
}
void updRange(int x
,int y
,int val
){
while(top
[x
]!=top
[y
]){
if(d
[top
[x
]]<d
[top
[y
]]) swap(x
,y
);
update(1,dfn
[top
[x
]],dfn
[x
],val
);
x
=fa
[top
[x
]];
}
if(d
[x
]>d
[y
]) swap(x
,y
);
update(1,dfn
[x
],dfn
[y
],val
);
}
int n
,m
;
void test(){
cout
<<"dfn"<<endl
;
for(int i
=1;i
<=n
;i
++)
printf("dfn[%d]=%d\n",i
,dfn
[i
]);
}
int main(){
cin
>>n
>>m
;
for(int i
=1;i
<=n
-1;i
++){
int x
,y
;
cin
>>x
>>y
;
addedge(x
,y
,1);
addedge(y
,x
,1);
}
dfs1(1,0);
dfs2(1,1);
build(1,1,n
);
while(m
--){
int x
,y
;
cin
>>x
>>y
;
updRange(x
,y
,1);
}
cout
<<query(1,1,n
)<<endl
;
return 0;
}
P3178 [HAOI2015]树上操作
#include<bits/stdc++.h>
using namespace std
;
const int N
=1e5+100;
#define ll long long
int head
[N
],ver
[N
<<1],edge
[N
<<1],nex
[N
<<1];
int tot
=0;
void addedge(int x
,int y
,int z
){
ver
[++tot
]=y
,nex
[tot
]=head
[x
],edge
[tot
]=z
;
head
[x
]=tot
;
}
int d
[N
];
int top
[N
];
int dfn
[N
];
int siz
[N
];
int son
[N
];
int rnk
[N
];
ll w
[N
];
int fa
[N
];
int cnt
=0;
#define lc (p<<1)
#define rc (p<<1|1)
#define mid ((t[p].l+t[p].r)>>1)
struct Segment
{
ll l
,r
;
ll dat
,alz
;
}t
[N
<<2];
void pushup(int p
){
t
[p
].dat
=t
[lc
].dat
+t
[rc
].dat
;
}
void build(int p
,int l
,int r
){
t
[p
].l
=l
,t
[p
].r
=r
;
t
[p
].alz
=0;
if(l
==r
){
t
[p
].dat
=w
[rnk
[l
]];
return ;
}
build(lc
,l
,mid
);
build(rc
,mid
+1,r
);
pushup(p
);
}
void spread(int p
){
if(t
[p
].alz
){
t
[lc
].dat
+=(t
[lc
].r
-t
[lc
].l
+1)*t
[p
].alz
;
t
[rc
].dat
+=(t
[rc
].r
-t
[rc
].l
+1)*t
[p
].alz
;
t
[lc
].alz
+=t
[p
].alz
;
t
[rc
].alz
+=t
[p
].alz
;
t
[p
].alz
=0;
}
}
ll
query(int p
,int l
,int r
){
if(l
<=t
[p
].l
&&t
[p
].r
<=r
) {
return t
[p
].dat
;
}
spread(p
);
ll val
=0;
if(l
<=mid
) val
=(val
+query(lc
,l
,r
));
if(r
>mid
) val
=(val
+query(rc
,l
,r
));
return val
;
}
void update(int p
,int l
,int r
,ll val
){
if(l
<=t
[p
].l
&&t
[p
].r
<=r
){
t
[p
].dat
+=(t
[p
].r
-t
[p
].l
+1)*val
;
t
[p
].alz
=(t
[p
].alz
+val
);
return;
}
spread(p
);
if(l
<=mid
) update(lc
,l
,r
,val
);
if(r
>mid
) update(rc
,l
,r
,val
);
pushup(p
);
}
void dfs1(int x
,int f
){
d
[x
]=d
[f
]+1;
siz
[x
]=1;
fa
[x
]=f
;
int maxson
=-1;
for(int i
=head
[x
];i
;i
=nex
[i
]){
int y
=ver
[i
];
if(y
==f
) continue;
dfs1(y
,x
);
siz
[x
]+=siz
[y
];
if(siz
[y
]>maxson
) son
[x
]=y
,maxson
=siz
[y
];
}
}
void dfs2(int x
,int t
){
dfn
[x
]=++cnt
;
top
[x
]=t
;
rnk
[cnt
]=x
;
if(!son
[x
]) return;
dfs2(son
[x
],t
);
for(int i
=head
[x
];i
;i
=nex
[i
]){
int y
=ver
[i
];
if(y
!=son
[x
]&&y
!=fa
[x
])
dfs2(y
,y
);
}
}
void updDot(int x
,ll val
){
update(1,dfn
[x
],dfn
[x
],val
);
}
ll
qRange(int x
,int y
){
ll ans
=0;
while(top
[x
]!=top
[y
]){
if(d
[top
[x
]]<d
[top
[y
]]) swap(x
,y
);
ll res
=query(1,dfn
[top
[x
]],dfn
[x
]);
ans
=(ans
+res
);
x
=fa
[top
[x
]];
}
if(d
[x
]>d
[y
]) swap(x
,y
);
ll res
=query(1,dfn
[x
],dfn
[y
]);
ans
=(ans
+res
);
return ans
;
}
void updSon(int x
,ll val
){
update(1,dfn
[x
],dfn
[x
]+siz
[x
]-1,val
);
}
int main(){
int n
,m
;
cin
>>n
>>m
;
for(int i
=1;i
<=n
;i
++) cin
>>w
[i
];
for(int i
=1;i
<=n
-1;i
++){
int x
,y
;
cin
>>x
>>y
;
addedge(x
,y
,1);
addedge(y
,x
,1);
}
dfs1(1,0);
dfs2(1,1);
build(1,1,n
);
for(int i
=1;i
<=m
;i
++){
ll x
,k
,op
;
cin
>>op
;
if(op
==1){
cin
>>x
>>k
;
updDot(x
,k
);
}
else if(op
==2){
cin
>>x
>>k
;
updSon(x
,k
);
}
else{
cin
>>x
;
cout
<<qRange(1,x
)<<endl
;
}
}
return 0;
}
P3384 【模板】轻重链剖分
#include<bits/stdc++.h>
using namespace std
;
#define ll long long
const int N
=1e5+100;
#define gc getchar
int read(){
int res
=0,f
=1;
char ch
=gc();
while(!isdigit(ch
)) f
^=ch
=='-',ch
=gc();
while(isdigit(ch
)) res
=(res
<<1)+(res
<<3)+(ch
^48),ch
=gc();
return res
;
}
int tot
=0;
int head
[N
],edge
[N
<<1],ver
[N
<<1],nex
[N
<<1];
void addedge(int x
,int y
,int z
){
ver
[++tot
]=y
,nex
[tot
]=head
[x
];
edge
[tot
]=z
;head
[x
]=tot
;
}
int son
[N
],dfn
[N
],fa
[N
],rnk
[N
],cnt
=0;
int d
[N
],siz
[N
],top
[N
];
#define lc (p<<1)
#define rc (p<<1|1)
#define mid ((t[p].l+t[p].r)>>1)
struct Segment
{
int l
,r
;
ll dat
,alz
;
}t
[N
<<2];
int mod
;
int n
,root
,m
,w
[N
];
void pushup(int p
){
t
[p
].dat
=(t
[lc
].dat
+t
[rc
].dat
)%mod
;
}
void build(int p
,int l
,int r
){
t
[p
].l
=l
,t
[p
].r
=r
;
t
[p
].alz
=0;
if(l
==r
) {
t
[p
].dat
=rnk
[l
];
return;
}
build(lc
,l
,mid
);
build(rc
,mid
+1,r
);
pushup(p
);
}
void spread(int p
){
if(t
[p
].alz
){
t
[lc
].dat
+=(t
[lc
].r
-t
[lc
].l
+1)*t
[p
].alz
;
t
[lc
].dat
%=mod
;
t
[rc
].dat
+=(t
[rc
].r
-t
[rc
].l
+1)*t
[p
].alz
;
t
[rc
].dat
%=mod
;
t
[lc
].alz
=(t
[lc
].alz
+t
[p
].alz
)%mod
;
t
[rc
].alz
=(t
[rc
].alz
+t
[p
].alz
)%mod
;
t
[p
].alz
=0;
}
}
ll
query(int p
,int l
,int r
){
if(l
<=t
[p
].l
&&t
[p
].r
<=r
) {
return t
[p
].dat
;
}
spread(p
);
ll val
=0;
if(l
<=mid
) val
=(val
+query(lc
,l
,r
))%mod
;
if(r
>mid
) val
=(val
+query(rc
,l
,r
))%mod
;
return val
;
}
void update(int p
,int l
,int r
,int val
){
if(l
<=t
[p
].l
&&t
[p
].r
<=r
){
t
[p
].dat
+=(t
[p
].r
-t
[p
].l
+1)*val
;
t
[p
].dat
%=mod
;
t
[p
].alz
=(t
[p
].alz
+val
)%mod
;
return;
}
spread(p
);
if(l
<=mid
) update(lc
,l
,r
,val
);
if(r
>mid
) update(rc
,l
,r
,val
);
pushup(p
);
}
void dfs1(int x
,int f
){
d
[x
]=d
[f
]+1;
siz
[x
]=1;
fa
[x
]=f
;
int maxson
=-1;
for(int i
=head
[x
];i
;i
=nex
[i
]){
int y
=ver
[i
];
if(y
==f
) continue;
dfs1(y
,x
);
siz
[x
]+=siz
[y
];
if(siz
[y
]>maxson
) son
[x
]=y
,maxson
=siz
[y
];
}
}
void dfs2(int x
,int t
){
dfn
[x
]=++cnt
;
top
[x
]=t
;
rnk
[cnt
]=w
[x
];
if(!son
[x
]) return;
dfs2(son
[x
],t
);
for(int i
=head
[x
];i
;i
=nex
[i
]){
int y
=ver
[i
];
if(y
!=son
[x
]&&y
!=fa
[x
])
dfs2(y
,y
);
}
}
int qRange(int x
,int y
){
int ans
=0;
while(top
[x
]!=top
[y
]){
if(d
[top
[x
]]<d
[top
[y
]]) swap(x
,y
);
int res
=query(1,dfn
[top
[x
]],dfn
[x
]);
ans
=(ans
+res
)%mod
;
x
=fa
[top
[x
]];
}
if(d
[x
]>d
[y
]) swap(x
,y
);
int res
=query(1,dfn
[x
],dfn
[y
]);
ans
=(ans
+res
)%mod
;
return ans
;
}
void updRange(int x
,int y
,int val
){
val
%=mod
;
while(top
[x
]!=top
[y
]){
if(d
[top
[x
]]<d
[top
[y
]]) swap(x
,y
);
update(1,dfn
[top
[x
]],dfn
[x
],val
);
x
=fa
[top
[x
]];
}
if(d
[x
]>d
[y
]) swap(x
,y
);
update(1,dfn
[x
],dfn
[y
],val
);
}
int qSon(int x
){
int res
=query(1,dfn
[x
],dfn
[x
]+siz
[x
]-1);
return res
;
}
void updSon(int x
,int val
){
update(1,dfn
[x
],dfn
[x
]+siz
[x
]-1,val
);
}
int main(){
n
=read(),m
=read(),root
=read(),mod
=read();
for(int i
=1;i
<=n
;i
++) w
[i
]=read();
for(int i
=1;i
<=n
-1;i
++){
int x
=read(),y
=read();
addedge(x
,y
,1);
addedge(y
,x
,1);
}
dfs1(root
,0);
dfs2(root
,root
);
build(1,1,n
);
for(int i
=1;i
<=m
;i
++){
int op
=read();
int x
,y
,k
;
if(op
==1){
x
=read(),y
=read(),k
=read();
updRange(x
,y
,k
);
}
else if(op
==2){
x
=read(),y
=read();
printf("%d\n",qRange(x
,y
));
}
else if(op
==3){
x
=read(),k
=read();
updSon(x
,k
);
}
else if(op
==4){
x
=read();
printf("%d\n",qSon(x
));
}
}
return 0;
}
P3833 [SHOI2012]魔法树
#include<bits/stdc++.h>
using namespace std
;
#define ll long long
const int N
=1e5+100;
int head
[N
],edge
[N
<<1],ver
[N
<<1],nex
[N
<<1];
int tot
;
void addedge(int x
,int y
,int z
){
ver
[++tot
]=y
,nex
[tot
]=head
[x
];
edge
[tot
]=z
,head
[x
]=tot
;
}
int d
[N
];
int top
[N
];
int fa
[N
];
int siz
[N
];
int dfn
[N
];
int rnk
[N
];
int son
[N
];
int cnt
=0;
#define lc (p<<1)
#define rc (p<<1|1)
#define mid ((t[p].l+t[p].r)>>1)
struct Segment
{
int l
,r
;
ll dat
,alz
;
}t
[N
<<2];
void pushup(int p
){
t
[p
].dat
=t
[lc
].dat
+t
[rc
].dat
;
}
void build(int p
,int l
,int r
){
t
[p
].l
=l
,t
[p
].r
=r
;
t
[p
].alz
=0;
if(l
==r
){
t
[p
].dat
=0;
return;
}
build(lc
,l
,mid
);
build(rc
,mid
+1,r
);
pushup(p
);
}
void spread(int p
){
if(t
[p
].alz
){
t
[lc
].dat
+=(t
[lc
].r
-t
[lc
].l
+1)*t
[p
].alz
;
t
[rc
].dat
+=(t
[rc
].r
-t
[rc
].l
+1)*t
[p
].alz
;
t
[lc
].alz
+=t
[p
].alz
;
t
[rc
].alz
+=t
[p
].alz
;
t
[p
].alz
=0;
}
}
void update(int p
,int l
,int r
,ll val
){
if(l
<=t
[p
].l
&&t
[p
].r
<=r
){
t
[p
].dat
+=(t
[p
].r
-t
[p
].l
+1)*val
;
t
[p
].alz
+=val
;
return;
}
spread(p
);
if(l
<=mid
) update(lc
,l
,r
,val
);
if(r
>mid
) update(rc
,l
,r
,val
);
pushup(p
);
}
ll
query(int p
,int l
,int r
){
if(l
<=t
[p
].l
&&t
[p
].r
<=r
){
return t
[p
].dat
;
}
spread(p
);
ll val
=0;
if(l
<=mid
) val
+=query(lc
,l
,r
);
if(r
>mid
) val
+=query(rc
,l
,r
);
return val
;
}
void updRange(int x
,int y
,ll val
){
while(top
[x
]!=top
[y
]){
if(d
[top
[x
]]<d
[top
[y
]]) swap(x
,y
);
update(1,dfn
[top
[x
]],dfn
[x
],val
);
x
=fa
[top
[x
]];
}
if(d
[x
]>d
[y
]) swap(x
,y
);
update(1,dfn
[x
],dfn
[y
],val
);
}
ll
qSon(int x
){
return query(1,dfn
[x
],dfn
[x
]+siz
[x
]-1);
}
void dfs1(int x
,int f
){
fa
[x
]=f
;
siz
[x
]=1;
d
[x
]=d
[f
]+1;
ll maxson
=-1;
for(int i
=head
[x
];i
;i
=nex
[i
]){
int y
=ver
[i
];
if(y
==f
) continue;
dfs1(y
,x
);
siz
[x
]+=siz
[y
];
if(maxson
<siz
[y
]) son
[x
]=y
,maxson
=siz
[y
];
}
}
void dfs2(int x
,int t
){
top
[x
]=t
;
dfn
[x
]=++cnt
;
rnk
[cnt
]=x
;
if(!son
[x
]) return;
dfs2(son
[x
],t
);
for(int i
=head
[x
];i
;i
=nex
[i
]){
int y
=ver
[i
];
if(y
!=fa
[x
]&&y
!=son
[x
])
dfs2(y
,y
);
}
}
int main(){
int n
;
cin
>>n
;
for(int i
=1;i
<=n
-1;i
++){
int x
,y
;
cin
>>x
>>y
;
x
++,y
++;
addedge(x
,y
,1);
addedge(y
,x
,1);
}
dfs1(1,0);
dfs2(1,1);
build(1,1,n
);
int m
;
cin
>>m
;
while(m
--){
char op
;
int x
,y
;
ll val
;
cin
>>op
;
if(op
=='A'){
cin
>>x
>>y
>>val
;
x
++,y
++;
updRange(x
,y
,val
);
}
else if(op
=='Q'){
cin
>>x
;
x
++;
cout
<<qSon(x
)<<endl
;
}
}
return 0;
}
P4092 [HEOI2016/TJOI2016]树
#include<bits/stdc++.h>
using namespace std
;
#define ll long long
const int N
=1e5+100;
int head
[N
],ver
[N
<<1],edge
[N
<<1],nex
[N
<<1];
int tot
=0;
void addedge(int x
,int y
,int z
){
ver
[++tot
]=y
,nex
[tot
]=head
[x
];
edge
[tot
]=z
,head
[x
]=tot
;
}
int d
[N
];
int cnt
=0;
int siz
[N
];
int top
[N
];
int son
[N
];
int fa
[N
];
int rnk
[N
];
int dfn
[N
];
#define lc (p<<1)
#define rc (p<<1|1)
#define mid ((t[p].l+t[p].r)>>1)
struct Segment
{
int l
,r
;
ll dat
;
}t
[N
<<2];
void pushup(int p
){
t
[p
].dat
=max(t
[lc
].dat
,t
[rc
].dat
);
}
void build(int p
,int l
,int r
){
t
[p
].l
=l
,t
[p
].r
=r
;
t
[p
].dat
=-1;
if(l
==r
) return;
build(lc
,l
,mid
);
build(rc
,mid
+1,r
);
}
void update(int p
,int l
,int r
){
if(l
<=t
[p
].l
&&t
[p
].r
<=r
){
t
[p
].dat
=t
[p
].l
;
return;
}
if(l
<=mid
) update(lc
,l
,r
);
if(r
>mid
) update(rc
,l
,r
);
pushup(p
);
}
int query(int p
,int l
,int r
){
if(l
<=t
[p
].l
&&t
[p
].r
<=r
) return t
[p
].dat
;
int val
=-1;
if(l
<=mid
) val
=max(val
,query(lc
,l
,r
));
if(r
>mid
) val
=max(val
,query(rc
,l
,r
));
return val
;
}
void dfs1(int x
,int f
){
d
[x
]=d
[f
]+1;
siz
[x
]=1;
fa
[x
]=f
;
int maxson
=-1;
for(int i
=head
[x
];i
;i
=nex
[i
]){
int y
=ver
[i
];
if(y
==f
) continue;
dfs1(y
,x
);
siz
[x
]+=siz
[y
];
if(maxson
<siz
[y
]) maxson
=siz
[y
],son
[x
]=y
;
}
}
void dfs2(int x
,int t
){
top
[x
]=t
;
dfn
[x
]=++cnt
;
rnk
[cnt
]=x
;
if(!son
[x
]) return;
dfs2(son
[x
],t
);
for(int i
=head
[x
];i
;i
=nex
[i
]){
int y
=ver
[i
];
if(y
!=fa
[x
]&&y
!=son
[x
])
dfs2(y
,y
);
}
}
void updRange(int x
,int y
){
if(top
[x
]!=top
[y
]){
if(d
[top
[x
]]<d
[top
[y
]]) swap(x
,y
);
update(1,dfn
[top
[x
]],dfn
[x
]);
x
=fa
[top
[x
]];
}
if(d
[x
]>d
[y
]) swap(x
,y
);
update(1,dfn
[x
],dfn
[y
]);
}
int qRange(int x
,int y
){
int ans
=-1;
while(top
[x
]!=top
[y
]){
if(d
[top
[x
]]<d
[top
[y
]]) swap(x
,y
);
ans
=query(1,dfn
[top
[x
]],dfn
[x
]);
if(ans
!=-1) return rnk
[ans
];
x
=fa
[top
[x
]];
}
if(d
[x
]>d
[y
]) swap(x
,y
);
ans
=query(1,dfn
[x
],dfn
[y
]);
return rnk
[ans
];
}
int main(){
int n
,m
;
cin
>>n
>>m
;
for(int i
=1;i
<=n
-1;i
++){
int x
,y
;
cin
>>x
>>y
;
addedge(x
,y
,1);
addedge(y
,x
,1);
}
dfs1(1,0);
dfs2(1,1);
build(1,1,n
);
updRange(1,1);
for(int i
=1;i
<=m
;i
++){
char op
;
int x
;
cin
>>op
>>x
;
if(op
=='C'){
updRange(x
,x
);
}
else{
cout
<<qRange(1,x
)<<endl
;
}
}
return 0;
}
P4114 Qtree1
#include<bits/stdc++.h>
using namespace std
;
const int N
=1e5+100;
const int INF
=0x3f3f3f3f;
#define ll long long
int head
[N
],edge
[N
<<1],nex
[N
<<1],ver
[N
<<1];
int tot
=0;
void addedge(int x
,int y
,int z
){
ver
[++tot
]=y
,nex
[tot
]=head
[x
];
edge
[tot
]=z
,head
[x
]=tot
;
}
int d
[N
];
int cnt
=0;
int siz
[N
];
int top
[N
];
int son
[N
];
int fa
[N
];
int rnk
[N
];
int dfn
[N
];
int u
[N
],v
[N
],w
[N
];
#define lc (p<<1)
#define rc (p<<1|1)
#define mid ((t[p].l+t[p].r)>>1)
struct Segment
{
int l
,r
;
ll dat
;
}t
[N
<<2];
void pushup(int p
){
t
[p
].dat
=max(t
[lc
].dat
,t
[rc
].dat
);
}
void build(int p
,int l
,int r
){
t
[p
].l
=l
,t
[p
].r
=r
;
if(l
==r
){
t
[p
].dat
=w
[rnk
[l
]];
return;
}
build(lc
,l
,mid
);
build(rc
,mid
+1,r
);
pushup(p
);
}
void update(int p
,int l
,int r
,int val
){
if(l
<=t
[p
].l
&&t
[p
].r
<=r
){
t
[p
].dat
=val
;
return;
}
if(l
<=mid
) update(lc
,l
,r
,val
);
if(r
>mid
) update(rc
,l
,r
,val
);
pushup(p
);
}
ll
query(int p
,int l
,int r
){
if(l
<=t
[p
].l
&&t
[p
].r
<=r
){
return t
[p
].dat
;
}
ll val
=-INF
;
if(l
<=mid
) val
=max(val
,query(lc
,l
,r
));
if(r
>mid
) val
=max(val
,query(rc
,l
,r
));
return val
;
}
void dfs1(int x
,int f
){
fa
[x
]=f
;
d
[x
]=d
[f
]+1;
siz
[x
]=1;
int maxson
=-1;
for(int i
=head
[x
];i
;i
=nex
[i
]){
int y
=ver
[i
];
if(y
==f
) continue;
w
[y
]=edge
[i
];
dfs1(y
,x
);
siz
[x
]+=siz
[y
];
if(maxson
<siz
[y
]) maxson
=siz
[y
],son
[x
]=y
;
}
}
void dfs2(int x
,int t
){
top
[x
]=t
;
dfn
[x
]=++cnt
;
rnk
[cnt
]=x
;
if(!son
[x
]) return;
dfs2(son
[x
],t
);
for(int i
=head
[x
];i
;i
=nex
[i
]){
int y
=ver
[i
];
if(y
!=fa
[x
]&&y
!=son
[x
])
dfs2(y
,y
);
}
}
ll
qRange(int x
,int y
){
ll ans
=-1;
while(top
[x
]!=top
[y
]){
if(d
[top
[x
]]<d
[top
[y
]]) swap(x
,y
);
ans
=max(ans
,query(1,dfn
[top
[x
]],dfn
[x
]));
x
=fa
[top
[x
]];
}
if(d
[x
]>d
[y
]) swap(x
,y
);
ans
=max(ans
,query(1,dfn
[x
]+1,dfn
[y
]));
return ans
;
}
void updRange(int x
,int y
,int val
){
while(top
[x
]!=top
[y
]){
if(d
[top
[x
]]<d
[top
[y
]]) swap(x
,y
);
update(1,dfn
[top
[x
]],dfn
[x
],val
);
x
=fa
[top
[x
]];
}
if(d
[x
]>d
[y
]) swap(x
,y
);
update(1,dfn
[x
],dfn
[y
],val
);
}
int main(){
int n
;
cin
>>n
;
for(int i
=1;i
<=n
-1;i
++){
int x
,y
,z
;
cin
>>x
>>y
>>z
;
addedge(x
,y
,z
);
addedge(y
,x
,z
);
u
[i
]=x
,v
[i
]=y
;
}
dfs1(1,0);
dfs2(1,1);
build(1,1,n
);
while(1){
string op
;
int x
,y
;
cin
>>op
;
if(op
=="DONE") break;
else if(op
=="QUERY"){
cin
>>x
>>y
;
if(x
==y
) cout
<<0<<endl
;
else cout
<<qRange(x
,y
)<<endl
;
}
else{
int i
,k
;
cin
>>i
>>k
;
int x
=u
[i
],y
=v
[i
];
if(fa
[y
]==x
) swap(x
,y
);
updRange(x
,x
,k
);
}
}
return 0;
}
P4116 Qtree3
#include<bits/stdc++.h>
using namespace std
;
#define ll long long
const int N
=1e5+100;
const int INF
=0x3f3f3f3f;
int head
[N
],ver
[N
<<1],edge
[N
<<1],nex
[N
<<1];
int tot
=0;
void addedge(int x
,int y
,int z
){
ver
[++tot
]=y
,edge
[tot
]=z
;
nex
[tot
]=head
[x
],head
[x
]=tot
;
}
int d
[N
];
int dfn
[N
];
int rnk
[N
];
int siz
[N
];
int fa
[N
];
int son
[N
];
int top
[N
];
int cnt
=0;
#define lc (p<<1)
#define rc (p<<1|1)
#define mid ((t[p].l+t[p].r)>>1)
struct Segment
{
int l
,r
;
int dat
;
}t
[N
<<2];
void pushup(int p
){
t
[p
].dat
=min(t
[lc
].dat
,t
[rc
].dat
);
}
void build(int p
,int l
,int r
){
t
[p
].l
=l
,t
[p
].r
=r
;
t
[p
].dat
=INF
;
if(l
==r
) return;
build(lc
,l
,mid
);
build(rc
,mid
+1,r
);
pushup(p
);
}
void update(int p
,int l
,int r
){
if(l
<=t
[p
].l
&&t
[p
].r
<=r
){
if(t
[p
].dat
==INF
) t
[p
].dat
=t
[p
].l
;
else t
[p
].dat
=INF
;
return;
}
if(l
<=mid
) update(lc
,l
,r
);
if(r
>mid
) update(rc
,l
,r
);
pushup(p
);
}
int query(int p
,int l
,int r
){
if(l
<=t
[p
].l
&&t
[p
].r
<=r
){
return t
[p
].dat
;
}
int val
=INF
;
if(l
<=mid
) val
=min(val
,query(lc
,l
,r
));
if(r
>mid
) val
=min(val
,query(rc
,l
,r
));
return val
;
}
void dfs1(int x
,int f
){
fa
[x
]=f
;
d
[x
]=d
[f
]+1;
siz
[x
]=1;
int maxson
=-1;
for(int i
=head
[x
];i
;i
=nex
[i
]){
int y
=ver
[i
];
if(y
==f
) continue;
dfs1(y
,x
);
siz
[x
]+=siz
[y
];
if(maxson
<siz
[y
]) maxson
=siz
[y
],son
[x
]=y
;
}
}
void dfs2(int x
,int t
){
top
[x
]=t
;
dfn
[x
]=++cnt
;
rnk
[cnt
]=x
;
if(!son
[x
]) return;
dfs2(son
[x
],t
);
for(int i
=head
[x
];i
;i
=nex
[i
]){
int y
=ver
[i
];
if(y
!=fa
[x
]&&y
!=son
[x
])
dfs2(y
,y
);
}
}
void updDot(int x
){
update(1,dfn
[x
],dfn
[x
]);
}
int qRange(int x
,int y
){
int ans
=INF
;
while(top
[x
]!=top
[y
]){
if(d
[top
[x
]]<d
[top
[y
]]) swap(x
,y
);
ans
=min(ans
,query(1,dfn
[top
[x
]],dfn
[x
]));
x
=fa
[top
[x
]];
}
if(d
[x
]>d
[y
]) swap(x
,y
);
ans
=min(ans
,query(1,dfn
[x
],dfn
[y
]));
if(ans
==INF
) return -1;
else return rnk
[ans
];
}
int main(){
int n
,m
;
cin
>>n
>>m
;
for(int i
=1;i
<=n
-1;i
++){
int x
,y
;
cin
>>x
>>y
;
addedge(x
,y
,1);
addedge(y
,x
,1);
}
dfs1(1,0);
dfs2(1,1);
build(1,1,n
);
while(m
--){
int op
,x
;
cin
>>op
>>x
;
if(op
==0) updDot(x
);
else cout
<<qRange(1,x
)<<endl
;
}
return 0;
}
P4281 [AHOI2008]紧急集合 / 聚会
#include<bits/stdc++.h>
using namespace std
;
const int N
=5e5+100;
int head
[N
],nex
[N
<<1],edge
[N
<<1],ver
[N
<<1];
int tot
=0;
void addedge(int x
,int y
,int z
){
ver
[++tot
]=y
,nex
[tot
]=head
[x
];
edge
[tot
]=z
;head
[x
]=tot
;
}
int d
[N
];
int fa
[N
];
int dfn
[N
];
int cnt
=0;
int siz
[N
];
int top
[N
];
int son
[N
];
void dfs1(int x
,int f
){
d
[x
]=d
[f
]+1;
siz
[x
]=1;
fa
[x
]=f
;
int maxson
=-1;
for(int i
=head
[x
];i
;i
=nex
[i
]){
int y
=ver
[i
];
if(y
==f
) continue;
dfs1(y
,x
);
siz
[x
]+=siz
[y
];
if(maxson
<siz
[y
]) maxson
=siz
[y
],son
[x
]=y
;
}
}
void dfs2(int x
,int t
){
top
[x
]=t
;
dfn
[x
]=++cnt
;
if(!son
[x
]) return;
dfs2(son
[x
],t
);
for(int i
=head
[x
];i
;i
=nex
[i
]){
int y
=ver
[i
];
if(y
!=fa
[x
]&&y
!=son
[x
])
dfs2(y
,y
);
}
}
int getlca(int x
,int y
){
while(top
[x
]!=top
[y
]){
if(d
[top
[x
]]<d
[top
[y
]]) swap(x
,y
);
x
=fa
[top
[x
]];
}
if(d
[x
]<d
[y
]) return x
;
else return y
;
}
int getdist(int x
,int y
){
return d
[x
]+d
[y
]-2*d
[getlca(x
,y
)];
}
int main(){
int n
,m
;
cin
>>n
>>m
;
for(int i
=1;i
<=n
-1;i
++){
int x
,y
;
cin
>>x
>>y
;
addedge(x
,y
,1);
addedge(y
,x
,1);
}
dfs1(1,0);
dfs2(1,1);
for(int i
=1;i
<=m
;i
++){
int x
,y
,z
;
cin
>>x
>>y
>>z
;
int c
=0x3f3f3f3f;
int ans
;
int lca
=getlca(x
,y
);
int dist
=getdist(x
,y
)+getdist(z
,lca
);
if(c
>dist
){
c
=dist
,ans
=lca
;
}
lca
=getlca(z
,y
);
dist
=getdist(z
,y
)+getdist(x
,lca
);
if(c
>dist
){
c
=dist
,ans
=lca
;
}
lca
=getlca(x
,z
);
dist
=getdist(x
,z
)+getdist(y
,lca
);
if(c
>dist
){
c
=dist
,ans
=lca
;
}
printf("%d %d\n",ans
,c
);
}
return 0;
}
P4315 月下“毛景树”
#include<bits/stdc++.h>
using namespace std
;
const int N
=1e5+100;
#define ll long long
int head
[N
],nex
[N
<<1],edge
[N
<<1],ver
[N
<<1];
int tot
=0;
void addedge(int x
,int y
,int z
){
ver
[++tot
]=y
,nex
[tot
]=head
[x
];
edge
[tot
]=z
,head
[x
]=tot
;
}
int d
[N
];
int top
[N
];
int dfn
[N
];
int rnk
[N
];
int fa
[N
];
int son
[N
];
int siz
[N
];
int cnt
=0;
int u
[N
],v
[N
],w
[N
];
#define lc (p<<1)
#define rc (p<<1|1)
#define mid ((t[p].l+t[p].r)>>1)
struct Segment
{
int l
,r
;
ll dat
,alz
,wlz
;
}t
[N
<<2];
void pushup(int p
){
t
[p
].dat
=max(t
[lc
].dat
,t
[rc
].dat
);
}
void build(int p
,int l
,int r
){
t
[p
].l
=l
,t
[p
].r
=r
;
t
[p
].alz
=0;
t
[p
].wlz
=-1;
if(l
==r
){
t
[p
].dat
=w
[rnk
[l
]];
return;
}
build(lc
,l
,mid
);
build(rc
,mid
+1,r
);
pushup(p
);
}
void spread(int p
){
if(t
[p
].wlz
>=0){
t
[lc
].dat
=t
[rc
].dat
=t
[p
].wlz
;
t
[lc
].wlz
=t
[rc
].wlz
=t
[p
].wlz
;
t
[lc
].alz
=t
[rc
].alz
=0;
t
[p
].wlz
=-1;
}
if(t
[p
].alz
){
t
[lc
].dat
+=t
[p
].alz
;
t
[rc
].dat
+=t
[p
].alz
;
t
[lc
].alz
+=t
[p
].alz
;
t
[rc
].alz
+=t
[p
].alz
;
t
[p
].alz
=0;
}
}
void updsame(int p
,int l
,int r
,int val
){
if(l
<=t
[p
].l
&&t
[p
].r
<=r
){
t
[p
].wlz
=val
;
t
[p
].alz
=0;
t
[p
].dat
=val
;
return;
}
spread(p
);
if(l
<=mid
) updsame(lc
,l
,r
,val
);
if(r
>mid
) updsame(rc
,l
,r
,val
);
pushup(p
);
}
void updadd(int p
,int l
,int r
,int val
){
if(l
<=t
[p
].l
&&t
[p
].r
<=r
){
t
[p
].alz
+=val
;
t
[p
].dat
+=val
;
return;
}
spread(p
);
if(l
<=mid
) updadd(lc
,l
,r
,val
);
if(r
>mid
) updadd(rc
,l
,r
,val
);
pushup(p
);
}
int query(int p
,int l
,int r
){
if(l
<=t
[p
].l
&&t
[p
].r
<=r
) return t
[p
].dat
;
spread(p
);
int val
=-1;
if(l
<=mid
) val
=max(val
,query(lc
,l
,r
));
if(r
>mid
) val
=max(val
,query(rc
,l
,r
));
return val
;
}
void dfs1(int x
,int f
){
fa
[x
]=f
;
d
[x
]=d
[f
]+1;
siz
[x
]=1;
int maxson
=-1;
for(int i
=head
[x
];i
;i
=nex
[i
]){
int y
=ver
[i
];
if(y
==f
) continue;
w
[y
]=edge
[i
];
dfs1(y
,x
);
siz
[x
]+=siz
[y
];
if(maxson
<siz
[y
]) maxson
=siz
[y
],son
[x
]=y
;
}
}
void dfs2(int x
,int t
){
top
[x
]=t
;
dfn
[x
]=++cnt
;
rnk
[cnt
]=x
;
if(!son
[x
]) return;
dfs2(son
[x
],t
);
for(int i
=head
[x
];i
;i
=nex
[i
]){
int y
=ver
[i
];
if(y
!=fa
[x
]&&y
!=son
[x
])
dfs2(y
,y
);
}
}
void UPD1(int x
,int y
,int val
){
while(top
[x
]!=top
[y
]){
if(d
[top
[x
]]<d
[top
[y
]]) swap(x
,y
);
updsame(1,dfn
[top
[x
]],dfn
[x
],val
);
x
=fa
[top
[x
]];
}
if(d
[x
]>d
[y
]) swap(x
,y
);
updsame(1,dfn
[x
]+1,dfn
[y
],val
);
}
void UPD2(int x
,int y
,int val
){
while(top
[x
]!=top
[y
]){
if(d
[top
[x
]]<d
[top
[y
]]) swap(x
,y
);
updadd(1,dfn
[top
[x
]],dfn
[x
],val
);
x
=fa
[top
[x
]];
}
if(d
[x
]>d
[y
]) swap(x
,y
);
updadd(1,dfn
[x
]+1,dfn
[y
],val
);
}
int qMax(int x
,int y
){
int ans
=-1;
while(top
[x
]!=top
[y
]){
if(d
[top
[x
]]<d
[top
[y
]]) swap(x
,y
);
ans
=max(ans
,query(1,dfn
[top
[x
]],dfn
[x
]));
x
=fa
[top
[x
]];
}
if(d
[x
]>d
[y
]) swap(x
,y
);
ans
=max(ans
,query(1,dfn
[x
]+1,dfn
[y
]));
return ans
;
}
int main(){
int n
;
cin
>>n
;
for(int i
=1;i
<=n
-1;i
++){
int x
,y
,z
;
cin
>>x
>>y
>>z
;
addedge(x
,y
,z
);
addedge(y
,x
,z
);
u
[i
]=x
,v
[i
]=y
;
}
dfs1(1,0);
dfs2(1,1);
build(1,1,n
);
while(1){
string op
;
int x
,y
,val
;
cin
>>op
;
if(op
=="Stop") break;
else if(op
=="Max"){
cin
>>x
>>y
;
cout
<<qMax(x
,y
)<<endl
;
}
else if(op
=="Cover"){
cin
>>x
>>y
>>val
;
UPD1(x
,y
,val
);
}
else if(op
=="Add"){
cin
>>x
>>y
>>val
;
UPD2(x
,y
,val
);
}
else{
int i
;
cin
>>i
>>val
;
int x
=u
[i
],y
=v
[i
];
if(fa
[y
]==x
) updsame(1,dfn
[y
],dfn
[y
],val
);
else updsame(1,dfn
[x
],dfn
[x
],val
);
}
}
return 0;
}
P4427 [BJOI2018]求和
#include<bits/stdc++.h>
const int N
=3e5+100;
#define inf 0x3f3f3f3f
#define ll long long
#define p 998244353
using namespace std
;
int n
,m
,cnt
;
int d
[N
],son
[N
],s
[N
][51],siz
[N
];
int top
[N
],fa
[N
];
int head
[N
],edge
[N
<<1],ver
[N
<<1],nex
[N
<<1];
int tot
=0;
void addedge(int x
,int y
,int z
){
ver
[++tot
]=y
,nex
[tot
]=head
[x
];
edge
[tot
]=z
;head
[x
]=tot
;
}
inline int power(int a
,int t
){
int res
= 1;
while(t
){
if(t
&1) res
= (ll
)res
*a
%p
;
a
= (ll
)a
*a
%p
;
t
>>= 1;
}
return res
;
}
inline void read(int &x
){
x
= 0;
char c
= getchar();
while(!isdigit(c
)) c
= getchar();
while(isdigit(c
)){
x
= (x
<<3)+(x
<<1)+c
-'0';
c
= getchar();
}
}
void print(int x
){
if(x
>9) print(x
/10);
putchar(x
%10+'0');
}
void dfs1(int x
,int f
){
fa
[x
]=f
;
d
[x
]=d
[f
]+1;
siz
[x
]=1;
ll maxson
=-1;
for(int i
=0;i
<=50;i
++){
s
[x
][i
]=(s
[f
][i
]+power(d
[x
]-1,i
))%p
;
}
for(int i
=head
[x
];i
;i
=nex
[i
]){
int y
=ver
[i
];
if(y
==f
) continue;
dfs1(y
,x
);
siz
[x
]+=siz
[y
];
if(maxson
<siz
[y
]) maxson
=siz
[y
],son
[x
]=y
;
}
}
void dfs2(int x
,int t
){
top
[x
]=t
;
if(!son
[x
]) return;
dfs2(son
[x
],t
);
for(int i
=head
[x
];i
;i
=nex
[i
]){
int y
=ver
[i
];
if(y
!=fa
[x
]&&y
!=son
[x
])
dfs2(y
,y
);
}
}
inline int lca(int u
,int v
){
int t
;
while(top
[u
]!=top
[v
]){
if(d
[top
[u
]]<d
[top
[v
]]){
t
= u
;
u
= v
;
v
= t
;
}
u
= fa
[top
[u
]];
}
if(d
[u
]<d
[v
]) return u
;
return v
;
}
int main(){
int u
,v
,k
,f
,ans
;
read(n
);
for(int i
=1;i
<n
;++i
){
read(u
),read(v
);
addedge(u
,v
,1);
addedge(v
,u
,1);
}
dfs1(1,0);
dfs2(1,1);
read(m
);
++m
;
while(--m
){
read(u
),read(v
),read(k
);
f
= lca(u
,v
);
ans
= (s
[u
][k
]+s
[v
][k
])%p
;
ans
-= (s
[f
][k
]+s
[fa
[f
]][k
])%p
;
ans
= (ans
+p
)%p
;
print(ans
);
putchar(10);
}
return 0;
}
