題目

‘

題解&思路

自己的思路：

感覺這還是一道較為簡單的樹剖題...（TM調了一天)

當詢問的x滿足

v是操作后最初的無視節點,now是當前時刻

然后轉化一下即可：

把每一個v放在lca上，這樣就是鏈修改鏈查詢了，然后直接上樹剖即可

可是為什么這道題調了一天呢？？還是一個細節問題：：

void change( int x , int u ){
    int t = dep[x] + u;
    if( top[x] != 1 ){
        modify( 1 , id[top[x]] , id[x] ,t );
        x = fa[top[x]];
    }
    modify( 1 , 1 , id[x] ,t );
}

TM把樹剖的修改寫成這樣了，，，，while寫成了if

細節部分一定要引以為戒，在用眼查的時候最好就先查出來！！！

代碼

#include <bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
const int MAXN = 1e5 + 3;
int n , m , head[MAXN] , cnt = 1;
int dep[MAXN] , dfn[MAXN] , zson[MAXN] , top[MAXN] ,fa[MAXN] , inde , id[MAXN] , siz[MAXN];
struct edge{
    int to , nex ;
}G[MAXN<<1];
void add_edge( int x, int y ){
    G[cnt].nex = head[x] , G[cnt].to = y;
    head[x] = cnt ++;
}
void dfs( int x , int f ){
    siz[x] = 1;
    for( int i = head[x] ; i ; i =G[i].nex ){
        int v = G[i].to;
        if( v == f ) continue;
        dep[v] = dep[x] + 1;
        fa[v] = x;
        dfs( v , x );
        siz[x] += siz[v];
        if( !zson[x] || siz[zson[x]] < siz[v] ) zson[x] = v;
    }
}
void dfs1( int x, int f ){
    top[x] = f;
    dfn[++inde] = x;id[x] = inde;
    if( !zson[x] ) return ;
    dfs1( zson[x] , f );
    for( int i = head[x] ; i ; i = G[i].nex ){
        int v =G[i].to;
        if( v == fa[x] || v == zson[x] ) continue;
        dfs1( v , v );
    }
}
struct tree{
    int l , r , lazy , minn , lazy1;
}tre[MAXN<<2];
void build( int i , int l , int r ){
    tre[i].l = l , tre[i].r = r , tre[i].lazy = tre[i].lazy1 = 0 , tre[i].minn = inf;
    if( l == r ) return ;
    int mid = l + r >> 1;
    build( i << 1 , l , mid );
    build( i << 1 | 1,  mid + 1, r );
}
void pushdown( int i ){
    if( tre[i].lazy1 ){
        tre[i<<1].minn = tre[i<<1|1].minn = inf , tre[i<<1].lazy1 = tre[i<<1|1].lazy1 = inf;
        tre[i<<1].lazy = tre[i<<1|1].lazy = 0;
        tre[i].lazy1 = 0 ;
    }
    if( tre[i].lazy ){
    	tre[i<<1].minn = min( tre[i<<1].minn , tre[i].lazy - 2 * dep[dfn[tre[i<<1].r]] );
    	if( !tre[i<<1].lazy ) tre[i<<1].lazy = tre[i].lazy;
    	else tre[i<<1].lazy = min( tre[i<<1].lazy , tre[i].lazy );
    	tre[i<<1|1].minn = min( tre[i<<1|1].minn , tre[i].lazy - 2 * dep[dfn[tre[i<<1|1].r]] );
    	if( !tre[i<<1|1].lazy ) tre[i<<1|1].lazy = tre[i].lazy;
    	else
            tre[i<<1|1].lazy = min( tre[i<<1|1].lazy , tre[i].lazy );
    	tre[i].lazy = 0;
	}
}
void modify( int i , int l , int r , int delta ){
    if( tre[i].l > r || tre[i].r < l ) return;
    if( tre[i].l >= l && tre[i].r <= r ){
        if( delta != inf ){
            tre[i].minn = min( tre[i].minn , delta - 2 * dep[dfn[tre[i].r]] );
            if( !tre[i].lazy ) tre[i].lazy = delta;
            else tre[i].lazy = min( delta , tre[i].lazy );
        }
        else{
            tre[i].lazy1 = inf , tre[i].minn = inf;//tre[i].lazy = 0;
        }
        return ;
    }
    pushdown( i );
    modify( i << 1 , l , r , delta );
    modify( i << 1 | 1, l , r , delta );
    tre[i].minn = min( tre[i<<1].minn , tre[i<<1|1].minn );
}
int query( int i , int l , int r ){
    if( tre[i].l > r || tre[i].r < l ) return inf;
    if( tre[i].l >= l && tre[i].r <= r ){
        return tre[i].minn;
    }
    pushdown( i );
    int ans = query( i << 1 , l , r );
    ans = min( ans , query( i << 1 | 1 , l , r )) ;
    tre[i].minn = min( tre[i<<1].minn , tre[i<<1|1].minn );
    return ans;
}
void change( int x , int u ){
    int t = dep[x] + u;
    if( top[x] != 1 ){
        modify( 1 , id[top[x]] , id[x] ,t );
        x = fa[top[x]];
    }
    modify( 1 , 1 , id[x] ,t );
}
void get_ans( int x , int u ){
    int t = u - dep[x];
    while( top[x] != 1 ){
        int tot = query( 1 , id[top[x]] , id[x] );
        if( tot <= t ){
            printf( "wrxcsd\n" );
            return ;
        }
        x = fa[top[x]];
    }
    int tot = query( 1 , 1 , id[x] );
    if( tot <= t )
        printf( "wrxcsd\n" );
    else
        printf( "orzFsYo\n" );
}
int main(){
	//freopen( "B.out" , "r" , stdin );
	//freopen( "C.out" , "w" , stdout );
    scanf( "%d%d" , &n , &m );
    dep[1] =1;
    for( int i = 1 ; i < n ; i ++ ){
        int x , y;scanf( "%d%d" , &x , &y );
        add_edge( x , y);
        add_edge( y , x );
    }
    dfs( 1,0 );
    dfs1( 1 , 1 );
    build( 1 , 1 , n );
    int u = 0;
    while( m -- ){
        u ++;
        int op , x;scanf( "%d%d" , &op , &x );
        if( op == 1 ){
            change( x , u );
        }
        else if( op == 2 )
            modify( 1 , 1 , n , inf );
        else{
            get_ans( x , u );
        }
    }
    return 0;
}