BZOJ 2819: Nim 트 리 배열 + lca + dfs 순서

Time Limit: 20 Sec Memory Limit: 128 MB Submit: 2998 Solved: 1120
Description
유명 게임 디자이너 vfleaking 이 최근 Nim 에 게 반 했다.일반적인 Nim 게임 은 두 사람 이 게임 을 하고 N 돌 을 쌓 으 며 매 라운드 에 그 중의 한 무더기 의 임의의 여러 개 를 취 할 수 있 으 며 다 취 할 수 있 지만 취하 지 않 으 면 안 된다.누가 이기 지 못 하면 누가 진다.이 게임 은 필승 전략 이 있다.그래서 vfleaking 은 Nim 게임 을 하 는 플랫폼 을 써 서 게이머 들 을 함정 에 빠 뜨리 기로 결정 했다.예 쁜 초기 국면 을 설계 하기 위해 vfleaking 은 다음 과 같은 방식 으로 영감 을 찾 습 니 다. 많은 돌 을 꺼 내 서 한 무더기 한 무더기 로 모 으 고 모든 번호 에 대해 1, 2, 3, 4.그리고 나 서 그 는 끊임없이 다음 과 같은 조작 을 했다.
1. 무 작위 로 두 개의 쌓 기 v, u 를 선택 하여 v 에서 u 사이 의 경로 에 있 는 돌 더미 에서 Nim 게임 을 하면 필승 전략 이 있 는 지 물 어 봅 니 다. 있 으 면 vfleaking 은 이 돌 더 미 를 초기 국면 중 하나 로 하여 게이머 들 을 함정 에 빠 뜨리 는 것 을 고려 할 것 입 니 다.2. 쌓 인 v 의 돌 수 를 k 로 바꾼다.
vfleaking 이 너무 게 을 러 서 그 는 스스로 손 을 대 는 것 이 귀찮다.프로그램 을 써 서 그 를 도와 주세요.
Input
첫 줄 에 n 을 세 는 것 은 돌 이 얼마나 쌓 여 있 는 지 를 나타 낸다.다음 줄 에서 i 번 째 수 는 i 더미 에 돌 이 얼마나 있 는 지 를 나타 낸다.다음 n - 1 줄 은 줄 마다 두 개의 수 v, u, 대표 v, u 사이 에 한 변 이 직접 연결 되 어 있다.다음 수 q 는 작업 의 개 수 를 나타 낸다.다음 q 줄 은 줄 마다 하나의 문자 가 있 습 니 다. Q 라면 뒤에 두 개의 v, u 가 있 습 니 다. v 에서 u 사이 의 경로 에 있 는 돌 더미 에서 Nim 게임 을 하면 필승 전략 이 있 는 지 물 어보 십시오.C 라면 뒤에 두 개의 수 v, k 가 있 는데 이것 은 쌓 인 v 중의 돌 수 를 k 로 바 꾸 는 것 을 의미한다.
100% 의 데이터 에 대하 여: 1 ≤ N ≤ 500000, 1 ≤ Q ≤ 500000, 0 ≤ 언제든지 돌 더미 의 개 수 ≤ 32767 중 30% 의 데이터: 돌 더미 가 하나의 체인 을 구성 하 였 으 며, 이 3 개 점 은 당신 의 DFS 시 스 택 을 폭발 시 킬 수 있 습 니 다 (당신 은 DFS 를 사용 하지 않 을 수 있 습 니까?).다른 데 이 터 는 DFS 눈대중 이 터 지지 않 습 니 다.
주의: 돌멩이 수의 범 위 는 0 에서 INT 입 니 다.MAX
Output
각 Q 에 대해 서 는 질문 에 대한 대답 을 나타 내 는 Yes 또는 No 줄 을 출력 합 니 다.
Sample Input
[샘플 입력]
5
1 3 5 2 5
1 5
3 5
2 5
1 4
6
Q 1 2
Q 3 5
C 3 7
Q 1 2
Q 2 4
Q 5 3
Sample Output
Yes
No
Yes
Yes
Yes
HINT
Source
호북성 팀 이 서로 측량 하 다.
솔직히 dfs 순 서 는 정말 좋 은 것 입 니 다. 우 리 는 먼저 dfs 에서 dfs 순 서 를 구 한 다음 에 fa 를 구 한 다음 에 우리 가 조회 할 때마다 x 와 y 의 lca 를 구 합 니 다. lca 를 구 한 후에 우리 의 답 은 x 에서 뿌리 까지 의 차이 나 차이 또는 Y 에서 뿌리 까지 의 차이 또는 차이 또는 lca 의 값 입 니 다. 그러면 우 리 는 이미 이 방향 이 있 습 니 다. 그 다음 에 수정 작업 을 어떻게 처리 합 니까?분명히 우리 의 dfs 순 서 는 이 문 제 를 해결 하 는 데 사용 할 수 있 습 니 다. 우 리 는 dfs 순 서 를 기록 한 후에 in 으로 수정 하고 out + 1 로 수정 할 수 있 습 니 다. 얼마 지나 지 않 아 in 에서 out 까지 구간 의 값 만 수정 하 였 습 니까?(즉, 이 점 의 서브 트 리 입 니 다. 곰 곰 이 생각해 보면 한 점 을 수정 하면 다른 점 에서 뿌리 까지 의 차이 나 합 에 영향 을 줄 수 있 습 니 다. 이런 점 들 은 이 점 의 서브 트 리 일 수 있 습 니 다. 다시 말 하면 한 점 을 수정 하면 이 점 의 서브 트 리 만 수정 할 수 있 습 니 다. 그리고 우리 가 in 을 수정 할 때 뒤의 모든 것 을 수정 하고 out + 1 을 수정 할 때 out + 1 에서 시작 한 모든 점 을 수정 합 니 다.돌 아 왔 습 니 다. 즉, 이 점 들 은 모두 영향 을 받 지 않 습 니 다. 다른 성질 에 주의 하 세 요. A ^ B ^ B = A) 그래서 우 리 는 즐겁게 해결 할 수 있 습 니 다.

#include
#include
#include
using namespace std;
int n, m, tail, timer ,in[500005], out[500005], a[500005], C[500005], pow[20], head[500005], dep[500005], fa[500005][20];;
struct line{ int to, nxt; } line[1000005];
void add_line( int from, int to ) { line[++tail].nxt = head[from]; head[from] = tail; line[tail].to = to; }
void modify( int x, int v ) { for( ; x <= n; x += x & -x ) C[x] ^= v; }
int query( int x ) { int tmp = 0; for( ; x; x -= x & -x ) tmp ^= C[x]; return tmp; }
void dfs( int u ) {
    for( register int i = 1; i <= 18; i++ )
    if( dep[u] >= pow[i] )
        fa[u][i] = fa[fa[u][ i - 1 ]][ i - 1 ];
    else break;
    in[u] = ++timer;
    for( register int i = head[u]; i; i = line[i].nxt ) {
        int v = line[i].to;
        if( v == fa[u][0] ) continue;
        dep[v] = dep[u] + 1;
        fa[v][0] = u;
        dfs(v);
    }
    out[u] = timer;
}
int lca( int x, int y ) {
    if( dep[x] < dep[y] )swap( x, y );
    int tmp = dep[x] - dep[y];
    for( register int i = 0; i <= 18; i++ ) 
        if( pow[i] & tmp ) x = fa[x][i]; 
    for( register int i = 18; i >= 0; i-- ) 
        if( fa[x][i] != fa[y][i] ) x = fa[x][i], y = fa[y][i];
    if( x == y )return x;
    return fa[x][0];
}
int main( ) {
    pow[0] = 1; for( register int i = 1; i < 20; i++ ) pow[i] = pow[ i - 1 ] << 1;
    scanf( "%d", &n );
    for( register int i = 1; i <= n; i++ ) scanf( "%d", &a[i] );
    for( register int i = 1; i <= n - 1; i++ ) { int ff, tt;
        scanf( "%d%d", &ff, &tt );
        add_line( ff, tt );add_line( tt, ff );
    }
    dfs(1);
    for( register int i = 1; i <= n; i++ ) modify( in[i], a[i] ), modify( out[i] + 1, a[i] );
    scanf( "%d", &m );
    for( register int i = 1; i <= m; i++ ) {
        char ch[10]; int x, y;
        scanf( "%s", ch );
        scanf( "%d%d", &x, &y );
        if( ch[0] == 'Q' ) {
            int fat = lca( x, y );
            int tmp = query( in[x] ) ^ query( in[y] ) ^ a[fat];
            if( tmp ) printf( "Yes
" );
            else      printf( "No
" );
        } else {
            modify( in[x], a[x] ); modify( out[x] + 1, a[x] );
            a[x] = y;
            modify( in[x], y ); modify( out[x] + 1, y ); 
        }
    }
    return 0;
}