看了下题，感觉直接最大生成树上差分然后树剖找LCA就稳定O(nlnn)了啊
by bzy369258147 @ 2018-09-29 10:12:59
好吧我链剖倍增都写了还是#15一直T
by jerry119 @ 2018-09-29 10:56:40
# include <bits/stdc++.h>
# define Rg register
const int N = 600000 + 5 ;
int head [ N ] , nxt [ N << 2 ] , to [ N << 2 ] , cn ;
int headx [ N ] , nxtx [ N << 2 ] , tox [ N << 2 ] , cnx ;
int belong [ N ] , num [ N << 2 ] , dfn [ N ] , low [ N ] , dep [ N ] , top [ N ] , seq [ N ] , son [ N ] , siz [ N ] , fa [ N ] ;
int wx [ N << 2 ] , w [ N << 2 ] , eat [ N ] , val [ N ] , s [ N ] , dian [ N ] , bian [ N ] ;
int dc , idc , x , y , n , m , q , pf , cnv , topx ;
bool ins [ N ] ;
/////////////////////////////////////////// tarjan ////////////////////////////////////////////////
inline void create ( int u , int v , int d ) {
cnx ++ ;
wx [ cnx ] = d ;
tox [ cnx ] = v ;
nxtx [ cnx ] = headx [ u ] ;
headx [ u ] = cnx ;
cnx ++ ;
wx [ cnx ] = d ;
tox [ cnx ] = u ;
nxtx [ cnx ] = headx [ v ] ;
headx [ v ] = cnx ;
num [ cnx - 1 ] = num [ cnx ] = cnx - 1 ;
}
inline void tarjan ( int u , int f ) {
idc ++ ;
dfn [ u ] = low [ u ] = idc ;
ins [ u ] = true ; s [ ++ topx ] = u ;
for ( int i = headx [ u ] ; i ; i = nxtx [ i ] ) {
int v = tox [ i ] ;
if ( num [ i ] != num [ f ] ) {
if ( ! dfn [ v ] ) {
tarjan ( v , i ) ;
low [ u ] = std :: min ( low [ u ] , low [ v ] ) ;
}
else if ( ins [ v ] ) low [ u ] = std :: min ( low [ u ] , dfn [ v ] ) ;
}
}
if ( dfn [ u ] == low [ u ] ) {
cnv ++ ;
while ( 1 ) {
int tmp = s [ topx -- ] ;
ins [ tmp ] = false ;
belong [ tmp ] = cnv ;
if ( tmp == u ) break ;
}
}
}
//////////////////////////////////////////// seg1 /////////////////////////////////////////////////
void build ( int u , int v , int d ) {
cn ++ ;
w [ cn ] = d ;
to [ cn ] = v ;
nxt [ cn ] = head [ u ] ;
head [ u ] = cn ;
}
void dfs1 ( int u , int f ) {
siz [ u ] = 1 ;
for ( int i = head [ u ] ; i ; i = nxt [ i ] ) {
int v = to [ i ] ;
if ( v == f ) continue ;
dep [ v ] = dep [ u ] + 1 ;
dian [ v ] = dian [ u ] + val [ v ] ;
bian [ v ] = bian [ u ] + w [ i ] ;
fa [ v ] = u ;
dfs1 ( v , u ) ;
siz [ u ] += siz [ v ] ;
if ( siz [ v ] > siz [ son [ u ] ] ) son [ u ] = v ;
}
}
void dfs2 ( int u , int tp ) {
top [ u ] = tp ;
if ( son [ u ] ) dfs2 ( son [ u ] , tp ) ;
for ( int i = head [ u ] ; i ; i = nxt [ i ] ) {
int v = to [ i ] ;
if ( v == fa [ u ] || v == son [ u ] ) continue ;
dfs2 ( v , v ) ;
}
}
int lca ( int u , int v ) {
while ( top [ u ] != top [ v ] ) {
if ( dep [ top [ u ] ] < dep [ top [ v ] ] ) u ^= v ^= u ^= v ;
u = fa [ top [ u ] ] ;
}
return dep [ u ] < dep [ v ] ? u : v ;
}
//////////////////////////////////////////// main /////////////////////////////////////////////////
int main ( ) {
scanf ( "%d%d" , & n , & m ) ;
for ( Rg int i = 1 ; i <= m ; i ++ ) {
scanf ( "%d%d%d" , & x , & y , & pf ) ;
create ( x , y , pf ) ;
}
for ( Rg int i = 1 ; i <= n ; i ++ )
if ( ! dfn [ i ] )
tarjan ( i , 0 ) ;
for ( Rg int i = 1 ; i <= n ; i ++ ) {
int tmp1 = belong [ i ] ;
for ( Rg int j = headx [ i ] ; j ; j = nxtx [ j ] ) {
int v = tox [ j ] ;
int tmp2 = belong [ v ] ;
if ( tmp1 != tmp2 )
build ( tmp1 , tmp2 , wx [ j ] ) ;
else if ( wx [ j ] )
val [ tmp1 ] = 1 ;
}
}
dep [ 1 ] = 1 ;
fa [ 1 ] = 1 ;
dfs1 ( 1 , 1 ) ;
dfs2 ( 1 , 1 ) ;
scanf ( "%d" , & q ) ;
for ( Rg int i = 1 ; i <= q ; i ++ ) {
scanf ( "%d%d" , & x , & y ) ;
if ( belong [ x ] == belong [ y ] ) {
if ( val [ belong [ x ] ] )
printf ( "YES\n" ) ;
else
printf ( "NO\n" ) ;
}
else {
int Lca = lca ( belong [ x ] , belong [ y ] ) ;
int tmp1 = bian [ belong [ x ] ] + bian [ belong [ y ] ] - 2 * bian [ Lca ] ;
int tmp2 = dian [ belong [ x ] ] + dian [ belong [ y ] ] - dian [ Lca ] - dian [ fa [ Lca ] ] ;
if ( tmp1 + tmp2 ) printf ( "YES\n" ) ;
else printf ( "NO\n" ) ;
}
}
return 0 ;
}
/*
2 5
1 3 1
1 3 0
1 2 1
3 1 0
1 3 0
2 5
1 1 1
1 1 1
1 1 0
1 2 0
2 2 1
1
1 2
*/
by jerry119 @ 2018-09-29 10:56:47
```cpp
# include <bits/stdc++.h>
# define Rg register
const int N = 600000 + 5 ;
int head [ N ] , nxt [ N << 2 ] , to [ N << 2 ] , cn ;
int headx [ N ] , nxtx [ N << 2 ] , tox [ N << 2 ] , cnx ;
int belong [ N ] , num [ N << 2 ] , dfn [ N ] , low [ N ] , dep [ N ] , top [ N ] , seq [ N ] , son [ N ] , siz [ N ] , fa [ N ] ;
int wx [ N << 2 ] , w [ N << 2 ] , eat [ N ] , val [ N ] , s [ N ] , dian [ N ] , bian [ N ] ;
int dc , idc , x , y , n , m , q , pf , cnv , topx ;
bool ins [ N ] ;
/////////////////////////////////////////// tarjan ////////////////////////////////////////////////
inline void create ( int u , int v , int d ) {
cnx ++ ;
wx [ cnx ] = d ;
tox [ cnx ] = v ;
nxtx [ cnx ] = headx [ u ] ;
headx [ u ] = cnx ;
cnx ++ ;
wx [ cnx ] = d ;
tox [ cnx ] = u ;
nxtx [ cnx ] = headx [ v ] ;
headx [ v ] = cnx ;
num [ cnx - 1 ] = num [ cnx ] = cnx - 1 ;
}
inline void tarjan ( int u , int f ) {
idc ++ ;
dfn [ u ] = low [ u ] = idc ;
ins [ u ] = true ; s [ ++ topx ] = u ;
for ( int i = headx [ u ] ; i ; i = nxtx [ i ] ) {
int v = tox [ i ] ;
if ( num [ i ] != num [ f ] ) {
if ( ! dfn [ v ] ) {
tarjan ( v , i ) ;
low [ u ] = std :: min ( low [ u ] , low [ v ] ) ;
}
else if ( ins [ v ] ) low [ u ] = std :: min ( low [ u ] , dfn [ v ] ) ;
}
}
if ( dfn [ u ] == low [ u ] ) {
cnv ++ ;
while ( 1 ) {
int tmp = s [ topx -- ] ;
ins [ tmp ] = false ;
belong [ tmp ] = cnv ;
if ( tmp == u ) break ;
}
}
}
//////////////////////////////////////////// seg1 /////////////////////////////////////////////////
void build ( int u , int v , int d ) {
cn ++ ;
w [ cn ] = d ;
to [ cn ] = v ;
nxt [ cn ] = head [ u ] ;
head [ u ] = cn ;
}
void dfs1 ( int u , int f ) {
siz [ u ] = 1 ;
for ( int i = head [ u ] ; i ; i = nxt [ i ] ) {
int v = to [ i ] ;
if ( v == f ) continue ;
dep [ v ] = dep [ u ] + 1 ;
dian [ v ] = dian [ u ] + val [ v ] ;
bian [ v ] = bian [ u ] + w [ i ] ;
fa [ v ] = u ;
dfs1 ( v , u ) ;
siz [ u ] += siz [ v ] ;
if ( siz [ v ] > siz [ son [ u ] ] ) son [ u ] = v ;
}
}
void dfs2 ( int u , int tp ) {
top [ u ] = tp ;
if ( son [ u ] ) dfs2 ( son [ u ] , tp ) ;
for ( int i = head [ u ] ; i ; i = nxt [ i ] ) {
int v = to [ i ] ;
if ( v == fa [ u ] || v == son [ u ] ) continue ;
dfs2 ( v , v ) ;
}
}
int lca ( int u , int v ) {
while ( top [ u ] != top [ v ] ) {
if ( dep [ top [ u ] ] < dep [ top [ v ] ] ) u ^= v ^= u ^= v ;
u = fa [ top [ u ] ] ;
}
return dep [ u ] < dep [ v ] ? u : v ;
}
//////////////////////////////////////////// main /////////////////////////////////////////////////
int main ( ) {
scanf ( "%d%d" , & n , & m ) ;
for ( Rg int i = 1 ; i <= m ; i ++ ) {
scanf ( "%d%d%d" , & x , & y , & pf ) ;
create ( x , y , pf ) ;
}
for ( Rg int i = 1 ; i <= n ; i ++ )
if ( ! dfn [ i ] )
tarjan ( i , 0 ) ;
for ( Rg int i = 1 ; i <= n ; i ++ ) {
int tmp1 = belong [ i ] ;
for ( Rg int j = headx [ i ] ; j ; j = nxtx [ j ] ) {
int v = tox [ j ] ;
int tmp2 = belong [ v ] ;
if ( tmp1 != tmp2 )
build ( tmp1 , tmp2 , wx [ j ] ) ;
else if ( wx [ j ] )
val [ tmp1 ] = 1 ;
}
}
dep [ 1 ] = 1 ;
fa [ 1 ] = 1 ;
dfs1 ( 1 , 1 ) ;
dfs2 ( 1 , 1 ) ;
scanf ( "%d" , & q ) ;
for ( Rg int i = 1 ; i <= q ; i ++ ) {
scanf ( "%d%d" , & x , & y ) ;
if ( belong [ x ] == belong [ y ] ) {
if ( val [ belong [ x ] ] )
printf ( "YES\n" ) ;
else
printf ( "NO\n" ) ;
}
else {
int Lca = lca ( belong [ x ] , belong [ y ] ) ;
int tmp1 = bian [ belong [ x ] ] + bian [ belong [ y ] ] - 2 * bian [ Lca ] ;
int tmp2 = dian [ belong [ x ] ] + dian [ belong [ y ] ] - dian [ Lca ] - dian [ fa [ Lca ] ] ;
if ( tmp1 + tmp2 ) printf ( "YES\n" ) ;
else printf ( "NO\n" ) ;
}
}
return 0 ;
}
/*
2 5
1 3 1
1 3 0
1 2 1
3 1 0
1 3 0
2 5
1 1 1
1 1 1
1 1 0
1 2 0
2 2 1
1
1 2
*/
```
by jerry119 @ 2018-09-29 10:57:01
@[bzy369258147](/space/show?uid=47240) 再调试5分钟不调了，难受
by jerry119 @ 2018-09-29 10:58:19
跪求 #15 数据 一直wa 不知道为什么
by chdy @ 2019-08-08 15:02:08