题意：给一棵树n个点，m次操作，每次把一条x到y的链涂一个Z颜色
问最后每个节点，对应被涂过最多的颜色是什么？
先树剖一下，变成： m次操作，每次给一个区间染色，最后问每个点被染过最多次的颜色是什么
这个问题的离线方法真的很巧妙啊。。。
根据颜色开一个线段树，第i位置表示颜色i出现过东西次 开一个vector<int> s[maxn], 假设在【l，r】中涂上颜色c，则s[l].push(c)，s[r+1].push(-c) 最后对每一个点i， 依次取出所有值， 如果s[i][j]==+c，则在线段树的位置c 加1，若==-c,则减一。 对于i的每个s[i][j],操作完取颜色线段树的最大值对应的颜色就是i点的答案 //BZOJ4034 #include <stdio.h> #include <string.h> #include <iostream> #include <algorithm> #include <vector> #include <queue> #include <set> #include <map> #include <string> #include <math.h> #include <stdlib.h> #include <time.h> #define lson l , m , rt << 1 #define rson m + 1 , r , rt << 1 | 1 using namespace std; typedef long long ll; const int MAXN = 100000+50; vector<int > s[MAXN]; struct Edge { int to,next; } edge[MAXN*2]; int head[MAXN],tot; int top[MAXN];//top[v]表示v所在的重链的顶端节点 int fa[MAXN]; //父亲节点 int deep[MAXN];//深度 int num[MAXN];//num[v]表示以v为根的子树的节点数 int p[MAXN];//p[v]表示v与其父亲节点的连边在线段树中的位置 int fp[MAXN];//和p数组相反 int son[MAXN];//重儿子 int pos; int out[MAXN];//dfs序 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++; } void dfs1(int u,int pre,int d) //第一遍dfs求出fa,deep,num,son { deep[u] = d; fa[u] = pre; num[u] = 1; for(int i = head[u]; i != -1; i = edge[i].next) { int v = edge[i].to; if(v != pre) { dfs1(v,u,d+1); num[u] += num[v]; if(son[u] == -1 || num[v] > num[son[u]]) son[u] = v; } } } void getpos(int u,int sp) //第二遍dfs求出top和p { top[u] = sp; p[u] = ++pos; fp[p[u]] = u; if(son[u]!=-1) getpos(son[u],sp); for(int i = head[u] ; i != -1; i = edge[i].next) { int v = edge[i].to; if(v != son[u] && v != fa[u]) getpos(v,v); } out[u]=pos; } const int maxn = 100000+5; struct TREE { int st_max[maxn<<2]; void build() { memset(st_max,0,sizeof st_max); } void PushUP(int rt) { st_max[rt] = max(st_max[rt<<1],st_max[rt<<1|1]); } void update(ll l,ll r,ll rt,ll num,ll val) { if (l == r&& l==num) { st_max[rt]+=val; return ; } ll m = (l + r) >> 1; if (num<=m) update(lson,num,val); else update(rson,num,val); PushUP(rt); } int query_max( int l,int r,int rt) //L,R为为查询区间，lr当前区间 { if (l==r) return l; int m = (l + r) >> 1; if (st_max[rt<<1]>=st_max[rt<<1|1]) return query_max( lson); else query_max( rson); } ll findsum(int u,int v,int z)//查询u->v链的sum { int f1=top[u],f2=top[v]; ll tmp=0; while(f1!=f2) { if (deep[f1]<deep[f2]) { swap(f1,f2); swap(u,v); } s[p[f1]].push_back(+z); s[p[u]+1].push_back(-z); //tmp+=(tmp,query(1,1,pos,p[f1],p[u])); u=fa[f1],f1=top[u]; } if (deep[u]>deep[v] ) swap(u,v); s[p[u]].push_back(+z); s[p[v]+1].push_back(-z); // return (tmp+ query(1,1,pos,p[u],p[v])); //若val(u)是u到fu的边权,则用son[u] } }; TREE tp; int ans[MAXN]; int main() { int n,m; while(scanf("%d%d",&n,&m)!=EOF) { if (!n&&!m) break; init(); for (int i=1; i<=n+1; i++) s[i].clear(); int u,v; for (int i=1; i<n; i++) { scanf("%d%d",&u,&v); addedge(u,v); addedge(v,u); } dfs1(1,0,0); getpos(1,1); tp.build(); int op,z; for (int i=1; i<=m; i++) { scanf("%d%d%d",&u,&v,&z); tp.findsum(u,v,z); } } return 0; }