Annoying problemTime Limit: 16000/8000 MS (Java/Others)Memory Limit: 65536/65536 K (Java/Others)Total Submission(s): 483Accepted Submission(s): 148
Problem Description
Coco has a tree, whose nodes are conveniently labeled by 1,2,…,n, which has n-1 edge，each edge has a weight. An existing set S is initially empty.Now there are two kinds of operation:1 x： If the node x is not in the set S, add node x to the set S2 x： If the node x is in the set S,delete node x from the set SNow there is a annoying problem: In order to select a set of edges from tree after each operation which makes any two nodes in set S connected. What is the minimum of the sum of the selected edges’ weight ?
Input
one integer number T is described in the first line represents the group number of testcases.( T<=10 )For each test:The first line has 2 integer number n,q(0<n,q<=100000) describe the number of nodes and the number of operations.The following n-1 lines each line has 3 integer number u,v,w describe that between node u and node v has an edge weight w.(1<=u,v<=n,1<=w<=100)The following q lines each line has 2 integer number x,y describe one operation.（x=1 or 2,1<=y<=n）
Output
Each testcase outputs a line of "Case #x:" , x starts from 1.The next q line represents the answer to each operation.
Sample Input
16 51 2 21 5 25 6 22 4 22 3 21 51 31 41 22 5
Sample Output
Case #1:06884
Author
FZUACM
题目大意：给出一棵树，每个边都有一个权值，，现在有一个空的集合，两种操作，1 x吧x节点放到集合中(如果还没放入)，2 x把x节点从集合中拿出来(已放入)。现在要求将集合中的点之间的边权之和
dfn[u] – dfn[ lca(x,u) ] – dfn[ lca(y,u) ] + dfn[ lca(x,y) ]
神一样的公式呀，表示比赛时根本就没想过要推公式，，，，，
先说这个公式怎么用，首先dfs一个顺序，加一个节点u，如果u节点的dfs序，在集合中节点的dfs序之间，那么找到最接近的(u的dfs序)的两个数为x和y；如果u节点的dfs序在集合中节点的dfs序的一侧，那么x和y为集合中dfs序的最大值和最小值，，，，，这样带入公式中求的就是添加这个节点所带来的需要添加的距离，删除一个节点和添加时一样的。
假设节点要连接到一个链中，链的定点(x,y)，那么u连接到x的距离是dfn[u] + dfn[x] – 2dfn[ lca(u,x) ] ;
u连接到y的距离dfn[u] + dfn[y] – 2dfn[ lca(u,x) ] :
x连接到y的距离dfn[x] + dfn[y] – 2dfn[ lca(x,y) ] :
u连接到x-y这个链的距离 = (u到y+u到x-x到y)/2
#include <cstdio>#include <cstring>#include <set>#include <algorithm>using namespace std ;#define maxn 100050struct E{int v , w ;int next ;}edge[maxn<<1];int head[maxn] , cnt ;int rmq[maxn][20] ;int dep[maxn] , p[maxn] , belong[maxn] , cid ;int vis[maxn] , dfn[maxn] ;set<int> s ;set<int>::iterator iter ;void add(int u,int v,int w) {edge[cnt].v = v ; edge[cnt].w = w ;edge[cnt].next = head[u] ; head[u] = cnt++ ;edge[cnt].v = u ; edge[cnt].w = w ;edge[cnt].next = head[v] ; head[v] = cnt++ ;}void dfs(int fa,int u) {int i , j , v ;p[u] = ++cid ;belong[cid] = u ;for(i = head[u] ; i != -1 ; i = edge[i].next ) {v = edge[i].v ;if( v == fa ) continue ;dfn[v] = dfn[u] + edge[i].w ;rmq[v][0] = u ;for(j = 1 ; j < 19 ; j++)rmq[v][j] = rmq[ rmq[v][j-1] ][j-1] ;dep[v] = dep[u] + 1 ;dfs(u,v) ;}}int lca(int u,int v) {if( dep[u] < dep[v] ) swap(u,v) ;int i ;for(i = 19 ; i >= 0 ; i–) {if( dep[ rmq[u][i] ] >= dep[v] )u = rmq[u][i] ;if( u == v ) return u ;}for(i = 19 ; i >= 0 ; i–) {if( rmq[u][i] != rmq[v][i] ) {u = rmq[u][i] ;v = rmq[v][i] ;}}return rmq[u][0] ;}int solve(int u) {if( s.empty() ) return 0 ;int x , y ;iter = s.upper_bound(u) ;if( iter == s.end() || iter == s.begin() ) {x = belong[ *s.begin() ] ;y = belong[ *s.rbegin() ] ;}else {x = belong[*iter] ;iter– ;y = belong[*iter] ;}u = belong[u] ;return dfn[u] – dfn[ lca(x,u) ] – dfn[ lca(y,u) ] + dfn[ lca(x,y) ] ;}int main() {int Step = 0 , t ;int n , m ;int i , j , u , v , w , k ;int ans ;scanf("%d", &t) ;while( t– ) {memset(head,-1,sizeof(head)) ;memset(rmq,0,sizeof(rmq)) ;memset(dfn,0,sizeof(dfn)) ;memset(vis,0,sizeof(vis)) ;cnt = cid = ans = 0 ;s.clear() ;scanf("%d %d", &n, &m) ;for(i = 1 ; i < n ; i++) {scanf("%d %d %d", &u, &v, &w) ;add(u,v,w) ;}dep[1] = 1 ;dfs(-1,1) ;printf("Case #%d:\n", ++Step) ;while( m– ) {scanf("%d %d", &k, &u) ;u = p[u] ;if( k == 1 ) {if( !vis[u] ) {vis[u] = 1 ;ans += solve(u) ;s.insert(u) ;}}else {if( vis[u] ) {vis[u] = 0 ;s.erase(u) ;ans -= solve(u) ;}}printf("%d\n", ans) ;}}return 0 ;}
版权声明：本文为博主原创文章，未经博主允许不得转载。
也不要说曾经失去，失去的不是永远失去，得到的不是永远拥有，
