hdu3710

/*

source:  http://acm.hdu.edu.cn/showproblem.php?pid=3710    2010 Asia Chengdu Regional Contest 

title:  Battle over Cities

题目简意：n个点，m条加权边，有些边已经被毁了，标记为0，有些边还可以用，标记为1。依次输出n个点，第i个数
表示第i个点被删除之后，把其余的点连起来需要的最小花费（一个点被删除之后，与之相连的边自然也就被删除了）
解法：
Kruskal + 树链剖分 + LCA
第一步：做一遍kruskal，生成一棵最小生成树minTree，花费为sum，并把没有进入最小生成树的边放在集合lea里。
第二步：对minTree做树链剖分，并计算ith[i](ith[i]表示节点i是其父节点的第ith[i]个儿子)的值。
第三步：对集合lea中的边做lca查询(这里我用tarjan算法)。设lea中某条边的两个端点为u和v，长度为len，
lca为anc。这里需要调用 handlelca函数做一些额外的事情：
  (1) 如果u和v都不等于anc，找出u和v到anc的路径上最靠近anc的点(除anc外)ku和kv。其实，ku就是u的第dep[u]
  -dep[anc]-1个父节点，v就是v的第dep[v]-dep[anc]-1个父节点，这个在剖分树上用log(n)的时间可以解决。
  然后把端点为ith[ku],ith[kv]，长度为len的边加进集合nes[anc]里。nes[anc]记录的是把anc删除之后可以用于
 把剩下的点连起来的边。
  (2)用len去更新从u到u的第(dep[u] - dep[anc] - 2)个父节点的路径上的每个点的pMin值(对v做同样的操作)。
   为了解释pMin的意义，定义点的集合Si,Si表示把节点i的父节点为根的子树去掉之后剩下的点组成的集合。pMin[i]就是表示i和
 Si中的点的边的最小值。这步更新操作作用在剖分树上，时间复杂度是O(log(n) * log(n))。


好了，有了这些准备，就可以求最后的答案了！
删除节点i的时候，剩下的点可以缩成sNum[i](sNum[i]表示节点i的直接后继的个数)个点和i的父节点(如果有的话),
至于为什么可以这样，我也没去证明，但由最小生成树的性质可以想到这点。至于可选的边，就包括了nes[i]中的边，
以及用i的子节点is和i的父节点pi组成的边，其长度为pMin[is]。把这些边加进ses集合，调用一遍kruskal函数得到ans，
如果ans为INF，最后的结果就是inf，否则，最后的结果就是sum - iw[i] + ans。


时间复杂度分析：第一步是O(m*log(m)); 第二步是O(n); 第三步求lca是O(m)，handlelca函数的时间复杂度是O(log(n)*log(n))，
共调用O(m-n)次; 第四步，可以这样来算，做了n次kruskal，涉及到的点的个数是生成树中的边的两倍，即O(2*n)个，涉及到的边的

数目是O(m+n)，故复杂度是O((m+n)log(m+n))。

代码比较长，有400多行…………

 */

 

#include <iostream>
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <ctime>
using namespace std;
const int N = 20005;
const int M = 100005;
const int QN = M;
const int INF = 0X7FFFFFFF;
typedef int vType;
typedef pair<int, int> pii;
#define mkpii make_pair<int, int>
struct e{
int v;
e* nxt;
}es[N<<1], *fir[N];
struct node{
    int ls, rs; //左右儿子的下标，为-1表示空
    int l, r;   //区间的左右标号
    //数据域
    int id;  //如果这个是叶子节点，id表示代表原树中的节点的标号
    vType Min;  //Min为这一整段插入的一个最小值
    int mid() { return (l + r) >> 1;  }
}nodes[N<<1];
struct se{
pii e;
int len;
}ses[M<<1], lea[M<<1];
int n, en, qn, m;


vector<pii> qlca[N];
vector<se> nes[N];
e stk[N];  //用于模拟dfs的数据结构
int par[N], fa[N]; //par[i]为i的直接前驱, fa用于并查集;
bool vis[N]; //标记节点是否已经访问
int  ln, cnt; //ln为链的数目,cnt为剖分树中节点的数目
int leaNum;
int  sons[N], que[N], dep[N], id[N], st[N], ed[N], root[N], top[N], sNum[N];
//sons[i]表示i为根的子树的大小，dep[i]表示节点的i的深度，id[i]为i所在链的标号,st和ed记录每条链的左右标号,root记录每条链的根节点的下标
//top[i]为第i条链的顶部节点,sNum[i]表示i的直接后继的个数
int ith[N], pMin[N], seg[N]; //ith[i]表示节点i是其父节点的第ith[i]个儿子(按访问顺序),
//seg在链上构建线段树的时候使用
vType iw[N];  //iw[i]表示节点i在最小生成树中与其他节点之间的边的权值的总和
int tr;  //最小生成树的根节点
void push(int u, int& top){
top++;
stk[top].v = u;
stk[top].nxt = fir[u];
fa[u] = u;
vis[u] = true;
}
int findFa(int u){
int k = u;
while(k != fa[k]) k = fa[k];
while(u != k){
int tf = fa[u];
fa[u] = k;
u = tf;
}
return k;
}
void merge(int u, int v){
int fu, fv;
fu = findFa(u);
fv = findFa(v);
fa[fu] = fv;
}
inline void add_e(int u, int v){
    es[en].v = v;
    es[en].nxt = fir[u];
    fir[u] = &es[en++];
}
inline void newNode(int& id, int l, int r){
    nodes[cnt].ls = nodes[cnt].rs = -1;
    nodes[cnt].l = l;
    nodes[cnt].r = r;
    nodes[cnt].Min = INF;
    id = cnt++;
}
void build(int& id, int l, int r){ //在剖分出来的链上构建线段树
newNode(id, l, r);
if(l >= r){
nodes[id].id = seg[l];
return ;
}
int mid = (l+r)>>1;
build(nodes[id].ls, l, mid);
build(nodes[id].rs, mid+1, r);
}
void initTree(){  //初始化剖分树
    //确定父亲
    int l, r, u, v, i;
    e* cur;
    l = r = 0;
    que[r++] = tr;
    par[tr] = -1;
    dep[tr] = 0;
    while(l != r){
        u = que[l++];
        int g = 1;
        for(cur = fir[u]; cur; cur = cur->nxt){
            if((v = cur->v) != par[u]){
                que[r++] = v;
                par[v] = u;
                dep[v] = dep[u]+1;
                ith[v] = g++;
            }
        }
    }
    //计算子树大小
    for(i = 1; i <= n; i++){
        sons[i] = 1;
        sNum[i] = 0;
        id[i] = -1;
    }
    for(i = r-1; i >= 0; i--){
    u = que[i];
        if(par[u] >= 0){
            sons[par[u]] += sons[u];
            sNum[par[u]]++;
        }
    }
    //剖分链
    l = r = 0;
    que[r++] = tr;
    ln = cnt = 0;
    while(l != r){
        u = que[l++];
        st[ln] = dep[u]; //用节点的深度作为线段树中区间的左右标号
        top[ln] = u;
        while(u >= 0){
            id[u] = ln;
            ed[ln] = dep[u];
            seg[dep[u]] = u;
            int best;
            for(cur = fir[u], best=-1; cur; cur = cur->nxt){
                if(id[v = cur->v] == -1){
                    if(best == -1 || (best >= 0 && sons[v] > sons[best])){
                        best = v;
                    }
                }
            }
            if(best >= 0){
                for(cur = fir[u]; cur; cur = cur->nxt){
                    if(id[v = cur->v] == -1 && best != v){
                        que[r++] = v;
                    }
                }
            }
            u = best;
        }
        root[ln] = -1;
        build(root[ln], st[ln], ed[ln]);
        ln++;
    }
}
int qrylKthFar(int& id, int i, int k){
//在链上查询i的第k个父节点(第0个为自己)
if(nodes[id].l == nodes[id].r) return nodes[id].id;
int mid = nodes[id].mid();
if(i - mid - 1 >= k) return qrylKthFar(nodes[id].rs, i, k);
else return qrylKthFar(nodes[id].ls, i, k);
}
int qryKthFar(int i, int k){
//查询i的第k个父节点(第0个为自己)
int u = i, ri;
while(true){
ri = id[u];
if(dep[u] - st[ri] >= k){
return qrylKthFar(root[ri], dep[u], k);
}else{
k -= dep[u] - st[ri] + 1;
u = par[top[ri]];
}
}
}
void inslMin(int& id, int ql, int qr, int mv){
    if(id == -1) return ;
    if(ql <= nodes[id].l && nodes[id].r <= qr){
    if(nodes[id].Min > mv){
    nodes[id].Min = mv;
    }
    return;
    }
    if(nodes[id].l == nodes[id].r) return;
    int mid = nodes[id].mid();
    if(ql <= mid){
        inslMin(nodes[id].ls, ql, qr, mv);
    }
    if(qr > mid){
        inslMin(nodes[id].rs, ql, qr, mv);
    }
}
void insMin(int i, int k, vType mv){  //在节点i和i的第k个父节点之间插入mv
int b, u;
u = i;
while(true){
b = id[u];
if(dep[u]-st[b] >= k){
inslMin(root[b], dep[u]-k, dep[u], mv);
return;
}else{
inslMin(root[b], st[b], dep[u], mv);
k -= dep[u] - st[b] + 1;
u = par[top[b]];
}
}
}


bool input(){
scanf("%d%d", &n, &m);
int i, k, tn;
for(i = tn = 0; i < m; i++){
scanf("%d%d%d%d", &ses[i].e.first, &ses[i].e.second, &ses[i].len, &k);
if(k == 1){  //既然这条边还在使用，可以把它的边权设为0
ses[i].len = 0;
}
if(ses[i].e.first != ses[i].e.second){
tn++;
}
}
m = tn;
return true;
}


inline bool cmp(se a, se b){
return a.len < b.len;
}


int kruskal(int n, int m, int& leaNum, bool flag){ //flag为true表示需要构图
int i, ans, k, u, v;
for(i = 1; i <= n; i++){
fa[i] = i;
}
if(flag){
for(i = 1; i <= n; i++){
iw[i] = 0;
fir[i] = NULL;
}
en = leaNum = 0;
}
sort(ses, ses + m, cmp);
for(i = ans = 0, k = 1; k < n && i < m; i++){
u = ses[i].e.first;
v = ses[i].e.second;
if(findFa(u) != findFa(v)){
ans += ses[i].len;
k++;
merge(u, v);
if(flag){
add_e(u, v);
add_e(v, u);
iw[u] += ses[i].len;
iw[v] += ses[i].len;
}
}else if(flag){ //这条边被剩出来
lea[leaNum++] = ses[i];
}
}
if (flag) {
for (; i < m; i++) {
lea[leaNum++] = ses[i];
}
}
if(k < n) ans = INF;
return ans;
}


void handlelca(int u, int v, int anc, int len){
if(u != anc && v != anc){
int ku, kv;
ku = qryKthFar(u, dep[u] - dep[anc] - 1);
kv = qryKthFar(v, dep[v] - dep[anc] - 1);
se te;
te.e.first = ith[ku];
te.e.second = ith[kv];
te.len = len;
nes[anc].push_back(te);
}
if(dep[anc] + 2 <= dep[u]){
insMin(u, dep[u] - dep[anc] - 2, len);
}
if(dep[anc] + 2 <= dep[v]){
insMin(v, dep[v] - dep[anc] - 2, len);
}
}
//qn为查询lca的次数，qs记录查询lca的两个几点，anc记录每次查询的结果
void lca(se* qs, int qn){
int i, r, u, v, top;
for(i = 1; i <= n; i++){
qlca[i].clear();
vis[i] = false;
nes[i].clear();
}
for(i = 0; i < qn; i++){
//这里的pii的first表示边长,second表示另一个点
qlca[qs[i].e.first].push_back(mkpii(qs[i].len, qs[i].e.second));
qlca[qs[i].e.second].push_back(mkpii(qs[i].len, qs[i].e.first));
}
r = tr;
top = -1;
push(r, top);
while(top >= 0){
u = stk[top].v;
if(!stk[top].nxt){ //u为根的子树已经访问完毕
if(par[u] >= 0){
fa[u] = par[u];
}
top--;
continue;
}
v = stk[top].nxt->v;
stk[top].nxt = stk[top].nxt->nxt;
if(v != par[u]){
push(v, top);
//处理查询
int size = qlca[v].size();
for(i = 0; i < size; i++){
int k = qlca[v][i].second;
if(!vis[k]) continue;
int anc = findFa(k); //anc为lca
handlelca(v, k, anc, qlca[v][i].first);
}
}
}
}
void getpMin(int& id, int mv){
if(mv > nodes[id].Min){
mv = nodes[id].Min;
}
if(nodes[id].l == nodes[id].r){
pMin[nodes[id].id] = mv;
return;
}
getpMin(nodes[id].ls, mv);
getpMin(nodes[id].rs, mv);
}
void getpMin(){
int i;
for(i = 0; i < ln; i++){
getpMin(root[i], INF);
}
}
void solve(){
tr = 1; //设置根节点
int sum, i, sn, v, num;
e* cur;
sum = kruskal(n, m, leaNum, true);
initTree();
lca(lea, leaNum);
getpMin();
for(i = 1; i <= n; i++){
num = 0;
sn = sNum[i];
if (par[i] >= 1) {
sn++;
for (cur = fir[i]; cur; cur = cur->nxt) {
if ((v = cur->v) != par[i] && pMin[v] < INF) {
ses[num].e.first = sn;
ses[num].e.second = ith[v];
ses[num].len = pMin[v];
num++;
}
}
}
int size = nes[i].size(), j;
for(j = 0; j < size; j++){
ses[num++] = nes[i][j];
}
int ans = kruskal(sn, num, leaNum, false);
if(ans < INF){
ans += sum - iw[i];
printf("%d\n", ans);
}else{
printf("inf\n");
}
}
}
int main() {
int t;
scanf("%d", &t);
while(t--){
input();
solve();
}
return 0;
}