代码有注释 ,自己康了下感觉没啥问题呀qwq 以下是代码
#include<bits/stdc++.h>
using namespace std ;
#define maxn 200005
#define int long long
#define kkk signed main
#define lc o<< 1
#define rc o << 1 | 1
inline int read(){
int ans = 0 , f = 1 ; char ch = getchar() ;
while ( ch < '0' || ch > '9') { if( ch == '-' ) f = -1 ; ch = getchar() ; }
while ( ch >= '0' && ch <= '9' ) ans = ( ans << 3 ) + ( ans << 1 ) + ch - '0' , ch = getchar() ;
return ans * f ;
}
int son[maxn] , siz[maxn] , top[maxn] , w[maxn] , mw[maxn] , fa[maxn] , dep[maxn];
// w存的是dfs序 mw存的是这个点的子树内最大的w
vector<int> G[maxn] ;
int data[maxn][3] , vis[maxn];
//data是存数据的 因为他问给第几条边加值
struct segtree{
int ll , rr , maa , sum , tag1 , add ;
//tag1 是有没有被cover add存的是加多少
}t[maxn << 2];
int n , dfsn;
int b[maxn] ;
//每个点的值
inline void dfs1(int u , int dp){
dep[u] = dp ; vis[u] = 1 ; siz[u] = 1 ;
int maxson = 0 ;
for(int i = 0 ; i < G[u].size() ; i++){
int v = G[u][i] ;
if(vis[v]) continue ;
dfs1(v , dp + 1) ;
fa[v] = u ;
siz[u] += siz[v] ;
if(siz[v] > maxson) son[u] = v , maxson = siz[v] ;
}
}
// 树拋第一步
inline int dfs2(int u , int tp){
w[u] = mw[u] = ++dfsn ;
top[u] = tp;
if(son[u])
mw[u] = max (mw[u] , dfs2(son[u] , tp)) ;
for(int i = 0 ; i < G[u].size() ; i++){
int v = G[u][i] ;
if(v == son[u] || v == fa[u])
continue ;
mw[u] = max(mw[u] , dfs2(v , v)) ;
}
return mw[u] ;
}
//第二步
inline void build(int o , int l , int r){
t[o].ll = l , t[o].rr = r ;
if(l == r){
t[o].sum = b[l] ;
t[o].maa = b[l] ;
return ;
}
int mid = (l + r) >> 1 ;
build(o << 1 , l , mid) , build(o << 1 | 1 , mid + 1 , r) ;
t[o].sum = t[lc].sum + t[rc].sum ;
t[o].maa = max(t[lc].maa , t[rc].maa) ;
return ;
}
//建树
inline void pushdown1(int o){
t[o].tag1 = 0 ;
t[lc].tag1 = 1 ; t[rc].tag1 = 1 ;
t[lc].maa = t[rc].maa = t[o].maa ;
t[lc].sum = t[lc].maa * (t[lc].rr - t[lc].ll + 1) ;
t[rc].sum = t[rc].maa * (t[rc].rr - t[rc].ll + 1) ;
return ;
}
// 关于是否被cover的标记下放
inline void update(int o , int l , int r , int val){
if(t[o].rr < l || t[o].ll > r) return ;
if(t[o].ll >= l && t[o].rr <= r){
t[o].sum = val * (t[o].rr - t[o].ll + 1);
t[o].maa = val ;
t[o].tag1 = 1 ;
return ;
}
// int mid = (t[o].l + t[o].r) >> 1 ;
if(t[o].tag1) pushdown1(o) ;
update(lc , l , r , val) ; update(rc , l , r , val) ;
t[o].sum = t[lc].sum + t[rc].sum ;
t[o].maa = max(t[lc].maa , t[rc].maa) ;
return ;
}
// 这里是cover操作
inline void pushdown2(int o ){
int a = t[o].add ;
t[o].add = 0 ;
t[lc].add += a ; t[rc].add += a ;
t[lc].maa +=a , t[rc].maa += a ;
t[lc].sum += a * (t[lc].rr - t[lc].ll + 1) ;
t[rc].sum += a * (t[rc].rr - t[rc].ll + 1) ;
return ;
}
//关于add的标记下放
inline void add(int o , int l , int r , int val){
if(t[o].rr < l || t[o].ll > r) return ;
if(t[o].ll >= l && t[o].rr <= r){
t[o].sum += val * (t[o].rr - t[o].ll + 1);
t[o].maa += val;
t[o].add = val ;
return ;
}
// int mid = (t[o].ll)
if(t[o].add) pushdown2(o) ;
add(lc , l , r , val) , add(rc , l , r , val) ;
t[o].sum = t[lc].sum + t[rc].sum ;
t[o].maa = max(t[lc].maa , t[rc].maa) ;
}
//add操作
inline int query(int o , int l , int r ){
if(t[o].rr < l || t[o].ll > r) return 0;
int res = 0 ;
if(t[o].ll >= l && t[o].rr <= r){
return t[o].maa ;
}
int mid = (t[o].ll + t[o].rr ) >> 1 ;
if(t[o].tag1 ) pushdown1(o) ;
if(t[o].add ) pushdown2(o) ;
if(mid >= l)
res = max(res , query(lc , l ,r)) ;
if(mid < r)
res = max(res , query(rc , l , r)) ;
// printf("o : %lld res : %lld\n" , o , res) ;
// printf("l : %lld r: %lld\n" , t[o].ll , t[o].rr ) ;
return res ;
}
inline int query_max(int x , int y){
int res = 0 ;
while(top[x] != top[y]){
if(dep[y] > dep[x])swap(x , y) ;
res = max(res , query(1 , w[top[x]] , w[x])) ;
// printf("w[%lld] : %lld top : %lld w : %lld\n " , x , w[x] , top[x] , w[top[x]]);
x = fa[top[x]] ;
}
if(dep[y] > dep[x]) swap(x , y) ;
res = max(res , query(1 , w[son[y]] ,w[x] )) ;
return res ;
}
//输入查询的两个点
inline void add_ (int x , int y , int val){
while(top[x] != top[y]){
if(dep[y] > dep[x])swap(x , y) ;
add(1 , w[top[x]] , w[x], val) ;
x = fa[top[x]] ;
}
if(dep[y] > dep[x]) swap(x , y) ;
add(1 , w[son[y]] , w[x] , val) ;
}
//同理qwq
inline void change(int x , int y , int val){
while(top[x] != top[y]){
if(dep[y] > dep[x])swap(x , y) ;
update(1 , w[top[x]], w[x] , val) ;
x = fa[top[x]] ;
}
if(dep[y] > dep[x]) swap(x , y) ;
update(1 , w[son[y]], w[x] , val) ;
}
//区间覆盖操作
inline void solve(){
char s[10] ; int x , y ;
while(1){
cin >> s ;
if(s[0] == 'S') break ;
x = read() , y = read() ;
if(s[0] == 'M' ) printf("%lld\n" , query_max(x , y)) ;
if(s[1] == 'h') {
change(data[x][1] , data[x][1] , y) ;
}
if(s[1] == 'o' ) {
int w = read() ;
change(x , y , w) ;
}
if(s[0] == 'A' ) {
int w = read() ;
add_(x , y , w) ;
}
}
}
kkk(){
// freopen("1.in" , "r" , stdin) ;
// freopen("1.out" , "w" ,stdout) ;
n = read() ;
for(int i = 1 ; i < n ; i++){
data[i][0] = read() , data[i][1] = read() , data[i][2] = read() ;
G[data[i][0]].push_back(data[i][1]) ;
G[data[i][1]].push_back(data[i][0]) ;
}
//存下数据
dfs1(1 , 1) ; dfs2(1 , 1) ;
for(int i = 1 ; i < n ; i++){
if(dep[data[i][0]]>dep[data[i][1]])
swap(data[i][0],data[i][1]);
b[w[data[i][1]]] = data[i][2] ;
//让更深的点获得点权 存值
}
build(1 , 1 , n) ;
solve() ;
// for(int i = 1 ; i <= n ; i++)
// printf("w[%lld] : %lld %lld\n" , i , w[i] , b[w[i]]) ;
return 0 ;
}
各位大佬走过路过不要错过啊啊啊啊啊啊啊qwq
谢谢谢谢谢谢
orz