题目性质比较显然，相同颜色联通块可以合并成一个点，重新建树后，发现相邻两个点的颜色一定是不一样的。
然后发现，对于一条链来说，每次把一个点反色，实际上使点数少了2个。如下图
而如果一条链上面有分支，也是一样：
所以我们实际上只需要把最长链上的变成一种颜色就可以了。最长链就是直径，需要改动的点就是$\frac{tot+1}{2}$,$tot$就是直径的点数。
（话说$stl$好慢aaa！！！要克制住我自己少用$map$叻！
#include<iostream>
#include<cstdio>
#include<map>
#include<cstring>
#include<algorithm>
using namespace std; int n, a[];
int stot, tov[], nex[], h[];
map < pair < int, int >, int > G; void add ( int u, int v ) {
tov[++stot] = v;
nex[stot] = h[u];
h[u] = stot;
} int stot_co, tov_co[], nex_co[], h_co[];
void add_co ( int u, int v ) {
tov_co[++stot_co] = v;
nex_co[stot_co] = h_co[u];
h_co[u] = stot_co;
} int fa[];
int find ( int x ) {
if ( x != fa[x] ) fa[x] = find ( fa[x] );
return x;
} void unionn ( int x, int y ) {
int xx = find ( x ), yy = find ( y );
fa[xx] = yy;
} int opt, color[];
void dfs1 ( int u, int f ) {
for ( int i = h[u]; i; i = nex[i] ) {
int v = tov[i];
if ( v == f ) continue;
color[v] = ;
if ( a[v] == a[u] ) color[v] = color[u];
else color[v] = ++ opt;
dfs1 ( v, u );
int x = find ( color[v] ), y = find ( color[u] );
if ( color[v] != color[u] && x != y ) {
add_co ( color[v], color[u] );
add_co ( color[u], color[v] );
unionn ( x, y );
}
}
} int dis[], rt;
void dfs ( int u, int f ) {
for ( int i = h_co[u]; i; i = nex_co[i] ) {
int v = tov_co[i];
if ( v == f ) continue;
dis[v] = dis[u] + ;
dfs ( v, u );
}
if ( dis[u] > dis[rt] ) rt = u;
} int main ( ) {
freopen ( "color.in", "r", stdin );
freopen ( "color.out", "w", stdout );
int T;
scanf ( "%d", &T );
while ( T -- ) {
G.clear ( );
stot = , stot_co = , opt = ;
scanf ( "%d", &n );
for ( int i = ; i <= n; i ++ ) h[i] = ;
for ( int i = ; i <= n; i ++ ) h_co[i] = ;
for ( int i = ; i <= n; i ++ ) color[i] = ;
for ( int i = ; i <= n; i ++ ) scanf ( "%d", &a[i] );
for ( int i = ; i < n; i ++ ) {
int u, v;
scanf ( "%d%d", &u, &v );
add ( u, v );
add ( v, u );
}
for ( int i = ; i <= n; i ++ ) fa[i] = i;
color[] = ++opt;
dfs1 ( , );
rt = ;
for ( int i = ; i <= opt; i ++ ) dis[i] = ;
dfs ( , );
for ( int i = ; i <= opt; i ++ ) dis[i] = ;
dfs ( rt, );
printf ( "%d\n", ( dis[rt] + ) / );
}
return ;
}
小模拟，考试的时候觉得状态太多，不可能重复？？？然后就没有写$vis$打标记，下来一加就...（辛酸泪QAQ
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<map>
using namespace std; int n, t[], G[][];
map < int, int > mx, my; struct node {
int x, y, opt, id;
node ( int x = , int y = , int opt = , int id = ) :
x ( x ), y ( y ), opt ( opt ), id ( id ) { }
};
queue < node > q;
int vis[][][][]; struct QAQ {
int x, y;
QAQ ( int x = , int y = ) :
x ( x ), y ( y ) { }
}; QAQ print ( int x, int y, int opt, int id ) {
for ( int i = ; i <= t[id]; i ++ ) {
G[x][y] = ;
x = x + mx[opt]; y = y + my[opt];
}
return QAQ ( x - mx[opt], y - my[opt] );
} void BFS ( int sx, int sy ) {
q.push ( node ( sx, sy + t[] - , , ) );
QAQ a = print ( sx, sy, , );
vis[sx][sy+t[]-][][] = ;
while ( !q.empty ( ) ) {
node x = q.front ( ); q.pop ( );
if ( x.id == n ) break;
if ( x.opt != - && x.opt != ) {
int L = x.opt - , R = x.opt + ;
int id = x.id + ;
int lsx = x.x + mx[L], lsy = x.y + my[L];
int rsx = x.x + mx[R], rsy = x.y + my[R];
QAQ ll = print ( lsx, lsy, L, id );
QAQ rr = print ( rsx, rsy, R, id );
if ( !vis[ll.x][ll.y][id][L] ) {
q.push ( node ( ll.x, ll.y, L, id ) );
vis[ll.x][ll.y][id][L] = ;
}
if ( !vis[rr.x][rr.y][id][R] ) {
q.push ( node ( rr.x, rr.y, R, id ) );
vis[rr.x][rr.y][id][R] = ;
}
} else if ( x.opt == - ) {
int L = , R = x.opt + ;
int id = x.id + ;
int lsx = x.x + mx[L], lsy = x.y + my[L];
int rsx = x.x + mx[R], rsy = x.y + my[R];
QAQ ll = print ( lsx, lsy, L, id );
QAQ rr = print ( rsx, rsy, R, id );
if ( !vis[ll.x][ll.y][id][L] ) {
q.push ( node ( ll.x, ll.y, L, id ) );
vis[ll.x][ll.y][id][L] = ;
}
if ( !vis[rr.x][rr.y][id][R] ) {
q.push ( node ( rr.x, rr.y, R, id ) );
vis[rr.x][rr.y][id][R] = ;
}
} else if ( x.opt == ) {
int L = x.opt - , R = -;
int id = x.id + ;
int lsx = x.x + mx[L], lsy = x.y + my[L];
int rsx = x.x + mx[R], rsy = x.y + my[R];
QAQ ll = print ( lsx, lsy, L, id );
QAQ rr = print ( rsx, rsy, R, id );
if ( !vis[ll.x][ll.y][id][L] ) {
q.push ( node ( ll.x, ll.y, L, id ) );
vis[ll.x][ll.y][id][L] = ;
}
if ( !vis[rr.x][rr.y][id][R] ) {
q.push ( node ( rr.x, rr.y, R, id ) );
vis[rr.x][rr.y][id][R] = ;
}
}
}
} int main ( ) {
freopen ( "grow.in", "r", stdin );
freopen ( "grow.out", "w", stdout );
scanf ( "%d", &n );
mx[] = , mx[] = , mx[] = , mx[] = , mx[] = , mx[-] = -, mx[-] = -, mx[-] = -;
my[] = , my[] = , my[] = , my[] = -, my[] = -, my[-] = , my[-] = , my[-] = -;
for ( int i = ; i <= n; i ++ ) scanf ( "%d", &t[i] );
BFS ( , );
int ans = ;
for ( int i = ; i < ; i ++ )
for ( int j = ; j < ; j ++ )
if ( G[i][j] ) ans ++;
printf ( "%d", ans );
}
有关串用$dp$解决是很显然的（？$idy$题解原话），定义$dp[s][t]$表示从$s$状态转移到$t$状态最少的修改数。关于状态定义代码有注释。用线段树维护区间状态转移$dp$值，每个节点保存一个矩阵，节点合并时类似$floyed$，枚举断点转移。查询时查询区间即可。
#include<iostream>
#include<cstdio>
#include<cstring>
#define oo 0x3f3f3f3f
using namespace std; // 0 1 2 3 4
// $ 2 20 201 2017 const int N = ; struct Info {
int dp[][];
void init ( int cur ) {
memset ( dp, 0x3f, sizeof ( dp ) );
if ( cur == || cur == || cur == || cur == || cur == ) {
for ( int i = ; i <= ; i ++ )
dp[i][i] = ;
} else if ( cur == ) {
dp[][] = ; dp[][] = ;
dp[][] = dp[][] = dp[][] = dp[][] = ;
} else if ( cur == ) {
dp[][] = ;
dp[][] = ;
dp[][] = dp[][] = dp[][] = dp[][] = ;
} else if ( cur == ) {
dp[][] = ;
dp[][] = ;
dp[][] = dp[][] = dp[][] = dp[][] = ;
} else if ( cur == ) {
dp[][] = ;
dp[][] = ;
dp[][] = dp[][] = dp[][] = dp[][] = ;
} else if ( cur == ) {
dp[][] = ;
dp[][] = ;
dp[][] = dp[][] = dp[][] = ;
}
}
}; Info operator + ( const Info &r, const Info &s ) {
Info rt;
memset ( &rt, 0x3f, sizeof ( rt ) );
for ( int i = ; i <= ; i ++ )
for ( int j = ; j <= ; j ++ )
for ( int k = i; k <= j; k ++ ) {
rt.dp[i][j] = min ( rt.dp[i][j], r.dp[i][k] + s.dp[k][j] );
}
return rt;
} struct node {
Info info;
node *ls, *rs;
} pool[N*], *tail = pool, *root; int a[N];
char s[N];
node *build ( int l, int r ) {
node *nd = ++tail;
if ( l == r ) {
nd -> info.init ( a[l] );
return nd;
}
int mid = ( l + r ) >> ;
nd -> ls = build ( l, mid );
nd -> rs = build ( mid + , r );
nd -> info = nd -> ls -> info + nd -> rs -> info;
return nd;
} Info query ( node *nd, int l, int r, int L, int R ) {
if ( l >= L && r <= R ) return nd -> info;
int mid = ( l + r ) >> ;
if ( R <= mid ) return query ( nd -> ls, l, mid, L, R );
else if ( L > mid ) return query ( nd -> rs, mid + , r, L, R );
else return query ( nd -> ls, l, mid, L, R ) + query ( nd -> rs, mid + , r, L, R );
} int n, q;
int query ( int l, int r ) {
Info info = query ( root, , n, l, r );
return info.dp[][] == oo ? - : info.dp[][];
} int main ( ) {
freopen ( "year.in", "r", stdin );
freopen ( "year.out", "w", stdout );
scanf ( "%s", s + );
scanf ( "%d", &q );
n = strlen ( s + );
for ( int i = ; i <= n; i ++ )
a[i] = s[i] - '';
root = build ( , n );
while ( q -- ) {
int l, r;
scanf ( "%d%d", &l, &r );
printf ( "%d\n", query ( l, r ) );
}
return ;
}