yjf1225 @ 2024-03-15 19:03:00
用重链剖分做的
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
using namespace std;
namespace akioi{
const int N=3e5+10;
const int INF=0x3f3f3f3f;
int n;
int h[N],ne[2*N],e[2*N],w[2*N],o[2*N],idx;
int sz[N],maxx[N],g[N];
int dfn[N],idx_dfn,sa[N];
int top[N],dep[N],fa[N],hei[N];
int Root,a[N],yjf[N];
struct node{
int maxx;
}tree[4*N];
void up(int k){
tree[k].maxx=max(tree[2*k].maxx,tree[2*k+1].maxx);
}
void build(int k,int l,int r){
if(l==r){
tree[k].maxx=dfn[l];
return ;
}
int mid=(l+r)>>1;
build(2*k,l,mid);
build(2*k+1,mid+1,r);
up(k);
}
int query(int k,int l,int r,int L,int R){
if(r<L || R<l) return 0;
if(L<=l && r<=R){
return tree[k].maxx;
}
int mid=(l+r)>>1;
return max(query(2*k,l,mid,L,R),query(2*k+1,mid+1,r,L,R));
}
void modify(int k,int l,int r,int L,int d){
if(r<L || L<l) return ;
if(l==r){
tree[k].maxx=d;
return ;
}
int mid=(l+r)>>1;
modify(2*k,l,mid,L,d);
modify(2*k+1,mid+1,r,L,d);
up(k);
}
void add(int x,int y,int z,int k){
e[++idx]=y;
w[idx]=z;
o[idx]=k;
ne[idx]=h[x];
h[x]=idx;
}
void dfs1(int u,int de,int last){
yjf[u]=last;
sz[u]=1;
for(int i=h[u];i!=-1;i=ne[i]){
if(last==o[i]) continue;
dep[o[i]]=de;
dfs1(e[i],de+1,o[i]);
sz[u]+=sz[e[i]];
fa[o[i]]=last;
if(sz[e[i]]>=maxx[u]){
maxx[u]=sz[e[i]];
g[u]=i;
}
}
}
void dfs2(int u,int tp,int last){
// cout<<u<<' '<<last<<'\n';
if(g[u]!=0){
dfn[++idx_dfn]=w[g[u]];
sa[o[g[u]]]=idx_dfn;
top[o[g[u]]]=tp;
dfs2(e[g[u]],tp,o[g[u]]);
}
for(int i=h[u];i!=-1;i=ne[i]){
if(o[i]!=last && i!=g[u]){
dfn[++idx_dfn]=w[i];
top[o[i]]=o[i];
sa[o[i]]=idx_dfn;
dfs2(e[i],o[i],o[i]);
}
}
}
int query_lca(int x,int y){
int ans=0;
while(top[x]!=top[y]){
// cout<<"!!!";
if(dep[top[x]]>dep[top[y]]){
ans=max(query(1,1,n,sa[top[x]],sa[x]),ans);
// cout<<"DDD"<<sa[top[x]]<<' '<<sa[x]<<'\n';
x=fa[top[x]];
}
else{
ans=max(query(1,1,n,sa[top[y]],sa[y]),ans);
// cout<<"DDD"<<sa[top[y]]<<' '<<sa[y]<<'\n';
y=fa[top[y]];
}
}
if(dep[x]>dep[y]){
ans=max(ans,query(1,1,n,sa[y]+1,sa[x]));
// cout<<sa[y]+1<<' '<<sa[x]<<'\n';
}
else{
ans=max(ans,query(1,1,n,sa[x]+1,sa[y]));
// cout<<x<<' '<<y<<' '<<sa[x]+1<<' '<<sa[y]<<'\n';
}
return ans;
}
int main(){
memset(h,-1,sizeof(h));
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);
// if(z==0) return 0;
}
dfn[++idx_dfn]=0;
sa[0]=1;
dfs1(1,1,0);
// cout<<"!!!";
dfs2(1,1,0);
build(1,1,n);
// for(int i=1;i<=n;i++){
// cout<<fa[i]<<'\n';
// }
char op[10];
for(int i=1;i;i++){
scanf("%s",op);
if(op[0]=='C'){
cin>>x>>y;
modify(1,1,n,sa[x],y);
}
else if(op[0]=='Q'){
cin>>x>>y;
if(x==y) printf("0\n");
else{
// cout<<yjf[x]<<' '<<yjf[y]<<'\n';
int tmp=query_lca(yjf[x],yjf[y]);
printf("%d\n",tmp);
}
}
else{
break;
}
}
return 0;
}
}
signed main(){
return akioi::main();
}
/*
5 1
1 2 1
2 3 100
3 4 2
1 5 3
1 5 2
*/by Enoch006 @ 2024-03-15 21:01:20
@yjf1225 就加个判断就行了啊
by Enoch006 @ 2024-03-15 21:02:31
@yjf1225 放学了，要不明天调(
by yjf1225 @ 2024-03-15 21:05:08
@Enoch006 ok
by yjf1225 @ 2024-03-16 16:28:02
@Enoch006 重构了一下代码，终于过了:
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<cstring>
using namespace std;
namespace fast_IO {
#define FASTIO
#define IOSIZE 100000
char ibuf[IOSIZE], obuf[IOSIZE];
char *p1 = ibuf, *p2 = ibuf, *p3 = obuf;
#ifdef ONLINE_JUDGE
#define getchar() ((p1==p2)and(p2=(p1=ibuf)+fread(ibuf,1,IOSIZE,stdin),p1==p2)?(EOF):(*p1++))
#define putchar(x) ((p3==obuf+IOSIZE)&&(fwrite(obuf,p3-obuf,1,stdout),p3=obuf),*p3++=x)
#endif//fread in OJ, stdio in local
#define isdigit(ch) (ch>47&&ch<58)
#define isspace(ch) (ch<33)
template<typename T> inline T read() {
T s = 0;
int w = 1;
char ch;
while (ch = getchar(), !isdigit(ch) and (ch != EOF)) if (ch == '-') w = -1;
if (ch == EOF) return false;
while (isdigit(ch)) s = s * 10 + ch - 48, ch = getchar();
return s * w;
}
template<typename T> inline bool read(T &s) {
s = 0;
int w = 1;
char ch;
while (ch = getchar(), !isdigit(ch) and (ch != EOF)) if (ch == '-') w = -1;
if (ch == EOF) return false;
while (isdigit(ch)) s = s * 10 + ch - 48, ch = getchar();
return s *= w, true;
}
inline bool read(char &s) {
while (s = getchar(), isspace(s));
return true;
}
inline bool read(char *s) {
char ch;
while (ch = getchar(), isspace(ch));
if (ch == EOF) return false;
while (!isspace(ch)) *s++ = ch, ch = getchar();
*s = '\000';
return true;
}
template<typename T> inline void print(T x) {
if (x < 0) putchar('-'), x = -x;
if (x > 9) print(x / 10);
putchar(x % 10 + 48);
}
inline void print(char x) {
putchar(x);
}
inline void print(char *x) {
while (*x) putchar(*x++);
}
inline void print(const char *x) {
for (int i = 0; x[i]; i++) putchar(x[i]);
}
#ifdef _GLIBCXX_STRING
inline bool read(std::string& s) {
s = "";
char ch;
while (ch = getchar(), isspace(ch));
if (ch == EOF) return false;
while (!isspace(ch)) s += ch, ch = getchar();
return true;
}
inline void print(std::string x) {
for (int i = 0, n = x.size(); i < n; i++)
putchar(x[i]);
}
#endif//string
template<typename T, typename... T1> inline int read(T& a, T1&... other) {
return read(a) + read(other...);
}
template<typename T, typename... T1> inline void print(T a, T1... other) {
print(a);
print(other...);
}
struct Fast_IO {
~Fast_IO() {
fwrite(obuf, p3 - obuf, 1, stdout);
}
} io;
template<typename T> Fast_IO& operator >> (Fast_IO &io, T &b) {
return read(b), io;
}
template<typename T> Fast_IO& operator << (Fast_IO &io, T b) {
return print(b), io;
}
#define cout io
#define cin io
#define endl '\n'
} using namespace fast_IO;
namespace akioi{
const int N=1e5+10;
const int INF=0x3f3f3f3f;
int n;
int h[N],ne[2*N],e[2*N],w[2*N],o[2*N],idx;
int dfn[N],sa[N],idx_dfn,sa2[N];
int dep[N],sz[N],maxx[N],g[N],top[N],fa[N];
struct node{
int maxx,sum;
}tree[4*N];
void add(int x,int y,int z,int k){
e[++idx]=y;
w[idx]=z;
o[idx]=k;
ne[idx]=h[x];
h[x]=idx;
}
void up(int k){
tree[k].sum=tree[2*k].sum+tree[2*k+1].sum;
tree[k].maxx=max(tree[2*k].maxx,tree[2*k+1].maxx);
}
void build(int k,int l,int r){
if(l==r){
tree[k].sum=tree[k].maxx=dfn[l];
return ;
}
int mid=(l+r)>>1;
build(2*k,l,mid);
build(2*k+1,mid+1,r);
up(k);
}
void modify(int k,int l,int r,int L,int d){
if(r<L || L<l) return ;
if(l==r){
tree[k].sum=tree[k].maxx=d;
return ;
}
int mid=(l+r)>>1;
modify(2*k,l,mid,L,d);
modify(2*k+1,mid+1,r,L,d);
up(k);
}
int query1(int k,int l,int r,int L,int R){
if(r<L || R<l) return -INF;
if(L<=l && r<=R){
return tree[k].maxx;
}
int mid=(l+r)>>1;
return max(query1(2*k,l,mid,L,R),query1(2*k+1,mid+1,r,L,R));
}
int query2(int k,int l,int r,int L,int R){
if(r<L || R<l) return 0;
if(L<=l && r<=R){
return tree[k].sum;
}
int mid=(l+r)>>1;
return query2(2*k,l,mid,L,R)+query2(2*k+1,mid+1,r,L,R);
}
void dfs(int u,int last,int deep){
dep[u]=deep;
sz[u]=1;
for(int i=h[u];i!=-1;i=ne[i]){
if(e[i]!=last){
dfs(e[i],u,deep+1);
fa[e[i]]=u;
sz[u]+=sz[e[i]];
if(sz[e[i]]>=maxx[u]){
maxx[u]=sz[e[i]];
g[u]=i;
}
}
}
}
void dfs2(int u,int last,int tp,int tmp){
// cout<<"???"<<u<<' '<<tp<<'\n';
sa2[o[tmp]]=u;
dfn[++idx_dfn]=w[tmp];
sa[u]=idx_dfn;
top[u]=tp;
if(g[u]!=0) dfs2(e[g[u]],u,tp,g[u]);
for(int i=h[u];i!=-1;i=ne[i]){
if(e[i]!=last && i!=g[u]){
dfs2(e[i],u,e[i],i);
}
}
}
int query_max(int x,int y){
int maxx=-INF;
while(top[x]!=top[y]){
if(dep[top[x]]>dep[top[y]]){
maxx=max(maxx,query1(1,1,n,sa[top[x]],sa[x]));
x=fa[top[x]];
}
else{
maxx=max(maxx,query1(1,1,n,sa[top[y]],sa[y]));
y=fa[top[y]];
}
}
if(dep[x]>dep[y]){
maxx=max(maxx,query1(1,1,n,sa[y]+1,sa[x]));
// cout<<"DDD"<<sa[y]<<' '<<sa[x]<<'\n';
}
else{
maxx=max(maxx,query1(1,1,n,sa[x]+1,sa[y]));
// cout<<"FFF"<<x<<'\n';
}
return maxx;
}
int query_sum(int x,int y){
int ans=0;
while(top[x]!=top[y]){
if(dep[top[x]]>dep[top[y]]){
ans+=query2(1,1,n,sa[top[x]],sa[x]);
x=fa[top[x]];
}
else{
ans+=query2(1,1,n,sa[top[y]],sa[y]);
y=fa[top[y]];
}
}
if(dep[x]>dep[y]){
ans+=query2(1,1,n,sa[y]+1,sa[x]);
}
else{
ans+=query2(1,1,n,sa[x]+1,sa[y]);
}
return ans;
}
int main(){
memset(h,-1,sizeof(h));
int m;
io>>n>>m;
// scanf("%d%d",&n,&m);
int x,y,z;
for(int i=1;i<n;i++){
// scanf("%d%d%d",&x,&y,&z);
io>>x>>y>>z;
add(x,y,z,i);
add(y,x,z,i);
}
// cout<<"!!!";
dfs(1,-1,1);
// cout<<"!!!";
dfs2(1,-1,1,0);
// cout<<"!!!";
build(1,1,n);
int op;
for(int i=1;i<=m;i++){
io>>op;
// scanf("%d",&op);
if(op==0){
io>>x>>y;
// cin>>x>>y;
modify(1,1,n,sa[sa2[x]],y);
// cout<<sa[sa2[x]]<<'\n';
}
else{
io>>x>>y;
// cin>>x>>y;
if(x==y) io<<"-1\n"; //printf("-1\n");
else{
int tmp=query_max(x,y);
io<<tmp<<'\n';
// printf("%d\n",tmp);
}
}
}
return 0;
}
}
signed main(){
return akioi::main();
} by Enoch006 @ 2024-03-16 16:36:52
@yjf1225 你哪儿错了啊qwq
by yjf1225 @ 2024-03-16 19:30:36
@Enoch006 之前我写的太复杂了，就重构了一下代码
by yjf1225 @ 2024-03-16 19:31:38
oj上还要加fast_io
by Enoch006 @ 2024-03-16 19:32:47
哦这样啊