2016-09-20

HDU 5893 List wants to travel【树链剖分】

题目链接：

http://acm.hdu.edu.cn/showproblem.php?pid=5893

题意：

给定树的边权，问对于给定的两点之间的路径上相邻相同的数有多少个？

分析：

很显然的树链剖分，用线段树维护区间内相邻相同数个数，并记录两端点元素值，合并的时候去一下重即可。
特别注意的是在链合并累加答案的时候要考虑到两条链接点处值是否相同。在这里wa了几百次。。。
整体思路非常显然，主要还是线段树那些的套路，但是细节的处理还是要十分仔细！

代码：

#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<cstdio>
#include<iostream>
#include<queue>
#include<cstring>
#include<stack>
#include<vector>
#include<algorithm>
#include<map>
#include<cmath>
using namespace std;
typedef long long ll;
const int maxn = 4e4 + 5, maxm = 4 * maxn;
struct Edge{int to; int next;}edge[maxn * 2];
int head[maxn];
int top[maxn];//重链的顶端节点
int fa[maxn];//父节点
int depth[maxn];//深度
int sz[maxn];//子树节点数
int p[maxn];//p[v]表示v与其父节点的连边在线段树中的位置
int fp[maxn];//连边对应的结点v
int son[maxn];//重儿子
int pos, tot;
int e[maxn][3];
#define lson (i << 1)
#define rson (i << 1 | 1)
//[l, r]
void init()
{
    tot = 0;
    memset(head, -1, sizeof(head));
    pos = 0;
    memset(son, -1, sizeof(son));
}
void addedge(int u, int v)
{
    edge[tot].to = v;
    edge[tot].next = head[u];
    head[u] = tot++;
    edge[tot].to = u;
    edge[tot].next = head[v];
    head[v] = tot++;
}
void dfs1(int now, int pre, int d)//??fa,depth, num, son
{
    depth[now] = d;
    fa[now] = pre;
    sz[now] = 1;
    for(int i = head[now]; i != -1; i = edge[i].next){
        int v = edge[i].to;
        if(v != pre){
            dfs1(v, now ,d + 1);
            sz[now] += sz[v];
            if(son[now] == -1 || sz[v] > sz[son[now]]) son[now] = v;
        }
    }
}
void dfs2(int now, int sp)
{
    top[now] = sp;
    if(son[now] != -1){
        p[now] = pos++;
        fp[p[now]] = now;
        dfs2(son[now], sp);
    }else{
        p[now] = pos++;
        fp[p[now]] = now;
        return;
    }
    for(int i = head[now]; i != -1; i = edge[i].next){
        int v = edge[i].to;
        if(v != son[now] && v != fa[now]) dfs2(v, v);
    }
}
struct Node{
    int l; int r; 
	int cnt; int lv; int rv;
    int lazy;
}segTree[maxm];
void push_up(int i)
{
    segTree[i].cnt = segTree[lson].cnt + segTree[rson].cnt;
    if(segTree[rson].lv == segTree[lson].rv)  --segTree[i].cnt;
    segTree[i].lv = segTree[i << 1].lv;
    segTree[i].rv = segTree[i << 1 | 1].rv;
}
void build(int i, int l, int r)
{
    segTree[i].cnt = 0;
    segTree[i].lv = segTree[i].rv = -1; 
    segTree[i].l = l;
    segTree[i].r = r;
    segTree[i].lazy = -1;
	if(l == r) return;
    int mid = l + r>>1;
    build(i<<1, l, mid);
    build((i << 1) | 1, mid + 1, r);
}
void push_down(int i)
{
	if(segTree[i].l == segTree[i].r) return;
    if(segTree[i].lazy != -1){
        segTree[lson].lazy = segTree[rson].lazy = segTree[i].lazy;
        segTree[rson].cnt = segTree[lson].cnt = segTree[i].cnt;
        segTree[lson].lv = segTree[rson].lv = segTree[i].lazy;
        segTree[lson].rv = segTree[rson].rv = segTree[i].lazy;
        segTree[i].lazy = -1;
    }
}
void update(int i, int l, int r, int x)
{
    if(segTree[i].l >= l && segTree[i].r <= r){
        segTree[i].cnt =  1;
        segTree[i].lazy = segTree[i].lv = segTree[i].rv = x;
        return;
    }
    push_down(i);
    int mid = segTree[i].l + segTree[i].r >> 1;
    if(r <= mid) update(i << 1, l, r, x);
    else if(l > mid) update((i << 1) | 1, l, r, x);
    else{
        update(i << 1, l, mid, x);
        update((i << 1) | 1, mid + 1, r, x);
    }
    push_up(i);
}
int query(int i, int l, int r)
{
    if(segTree[i].l >= l && segTree[i].r <= r) return segTree[i].cnt;
    int mid = segTree[i].l + segTree[i].r >> 1;
    push_down(i);
	if(r <= mid) return query(i << 1, l ,r);
    else if(l > mid) return query((i << 1) | 1, l, r);
    else {
        int ans = query(i << 1, l, mid) + query((i << 1)|1, mid + 1, r);
        if(segTree[lson].rv == segTree[rson].lv) ans--;
        return ans;
    }
}
int _find(int i, int x)
{
	if(segTree[i].l == segTree[i].r) return segTree[i].lv;
	int mid = segTree[i].l + segTree[i].r >> 1;
	push_down(i);
	if(x <= mid) return _find(lson, x);
	else return _find(rson, x);
}
int get(int u, int v)
{
    int f1 = top[u], f2 = top[v];
    int ans = 0;
	int lastu = -1, lastv = -1;
    while(f1 != f2){
		if(depth[f1] < depth[f2]){
			swap(f1, f2);
			swap(u, v);
			swap(lastu, lastv);
		}
		ans += query(1, p[f1], p[u]);
		if(_find(1, p[u]) == lastu) ans--;
		lastu = _find(1, p[f1]);
		u = fa[f1];
		f1 = top[u];
    }
    if(u == v) return lastv == lastu?ans - 1:ans;
    if(depth[u] > depth[v]) swap(u, v),swap(lastu, lastv);
	ans += query(1, p[son[u]], p[v]);
	if(_find(1, p[son[u]]) == lastu) ans--;
	if(_find(1, p[v]) == lastv) ans--;
    return ans;
}
void modify(int u, int v, int x)
{
	int f1 = top[u], f2 = top[v];
    while(f1 != f2){
        if(depth[f1] < depth[f2]){
            swap(f1, f2);
            swap(u, v);
        }   
        update(1, p[f1], p[u], x) ;
        u = fa[f1];
        f1 = top[u];
    }
	if(u == v) return;
    if(depth[u] > depth[v]) swap(u, v);
	update(1, p[son[u]], p[v], x);
}
int main (void)
{
    int n, m;
    while(~scanf("%d%d", &n, &m)){
        init();
        int u, v, x;
         for(int i = 0; i < n -1; i++){
            scanf("%d%d%d", &e[i][0], &e[i][1], &e[i][2]);
            addedge(e[i][0], e[i][1]);
        }
        dfs1(1, 0, 0);
        dfs2(1, 1);
        build(1, 0, pos - 1);
        for(int i = 0; i < n - 1; i++){
           if(depth[e[i][0]] > depth[e[i][1]]) swap(e[i][0], e[i][1]);
		   update(1, p[e[i][1]], p[e[i][1]], e[i][2]);
        }
        char c[10];
        int y;
        for(int i = 0; i < m; i++){
            scanf("%s", c);
            if(c[0] == 'Q'){
                scanf("%d%d", &x, &y);
				if(x == y) puts("0");
				else printf("%d\n", get(x, y));
            }else{
                scanf("%d%d%d", &x, &y, &v);
                modify(x, y, v);
            }
        } 
    }
    return 0;
}