题目
牛半仙的妹子的座位呈一个树状结构，由 n 个点和 n−1 条边组成， 1 号结点为根。 当牛半仙的一个妹子无视 牛半仙后，一个单位时间后周围的妹子也会无视牛半仙。 有些时候牛半仙为了吸引妹子们的注意，会开启鬼畜模式，这时所有妹子无视牛半仙的状态都会消失， 恢复正常，并且这之后的状态不会被之前影响。 牛半仙想知道某个妹子是否无视了他，于是他找到了你，请你帮帮他
‘
题解&思路
自己的思路：
感觉这还是一道较为简单的树剖题...（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;
}
