题意：n个点构成的无根树，m次操作， 对于操作 x y z， 表示 x 到 y 路径上的 每个点 加一个 z 数字，可重复加。最后输出每个点 加的次数最多的那个数字，如果没有输出0.
赤裸裸的树链剖分，可是剖分之后 怎么用线段树维护每个点加的数字的次数呢。这里用到的思想类似于2014年上海网络赛的一道题。HDU5044，假如[x,y]这个区间上所有的点加上数字z，可以用两个标记 vec[x] + z,vec[y+1] -c。HDU上C++提交竟然爆栈，不过G++还是顺利ac了。具体见代码
1 #include <cstdio> 2 #include <vector> 3 #include <cstdlib> 4 #include <cstring> 5 #include <algorithm> 6 using namespace std; 7 const int maxn = 1e5+10; 8 int siz[maxn],dep[maxn],son[maxn],fa[maxn]; 9 struct 10 { 11 int to,next; 12 }e[maxn<<1]; 13 int tot,head[maxn]; 14 void add_edge(int x,int y) 15 { 16 e[tot].to = y; 17 e[tot].next = head[x]; 18 head[x] = tot++; 19 } 20 void dfs(int r) 21 { 22 son[r] = 0; 23 siz[r] = 1; 24 for (int i = head[r]; ~i; i = e[i].next) 25 { 26 int u = e[i].to; 27 if (fa[r] != u) 28 { 29 dep[u] = dep[r] + 1; 30 fa[u] = r; 31 dfs(u); 32 if (siz[u] > siz[son[r]]) 33 son[r] = u; 34 siz[r] += siz[u]; 35 } 36 } 37 } 38 int top[maxn],pos[maxn],fp[maxn],idx; 39 void build(int r,int father) 40 { 41 pos[r] = ++idx; //记录每一个点 对应的位置 42 fp[pos[r]] = r; //记录每一个位置对应的点 43 top[r] = father; 44 if (son[r] > 0) 45 build(son[r],top[r]); 46 for (int i = head[r]; ~i; i = e[i].next) 47 { 48 if (fa[r] != e[i].to && son[r] != e[i].to) 49 build(e[i].to,e[i].to); 50 } 51 } 52 vector<int>vec[maxn]; 53 void update(int x,int y,int v) 54 { 55 int fx = top[x]; 56 int fy = top[y]; 57 while (fx != fy) 58 { 59 if (dep[fx] < dep[fy]) 60 { 61 swap(x,y),swap(fx,fy); 62 } 63 vec[pos[fx]].push_back(v); //有点类似于树状数组区间更新单点查询， 64 vec[pos[x] + 1].push_back(-v); 65 x = fa[fx]; 66 fx = top[x]; 67 } 68 if (dep[x] > dep[y]) 69 swap(x,y); 70 vec[pos[x]].push_back(v); 71 vec[pos[y] + 1].push_back(-v); 72 } 73 74 int n,m,seg[maxn<<2],max_pos[maxn<<2]; //max_pos为最大值在原始数组中的位置 75 void init() 76 { 77 int root = (1+n)/2; 78 idx = tot = 0; 79 dep[root] = fa[root] = 0; 80 memset(head,-1,sizeof(head)); 81 memset(siz,0,sizeof(siz)); 82 memset(seg,0,sizeof(seg)); 83 memset(max_pos,0,sizeof(max_pos)); 84 for (int i = 0; i < n - 1; i++) 85 { 86 int u,v; 87 scanf ("%d%d",&u,&v); 88 add_edge(u,v); 89 add_edge(v,u); 90 } 91 dfs(root); 92 build(root,root); 93 for (int i = 1; i <= n; i++) 94 vec[i].clear(); 95 for (int i = 0; i < m; i++) 96 { 97 int x,y,v; 98 scanf ("%d%d%d",&x,&y,&v); 99 update(x,y,v); 100 } 101 } 102 void update(int l,int r,int pos,int x,int val) 103 { 104 if (l == r) 105 { 106 seg[pos] += val; 107 if (seg[pos] > 0) 108 max_pos[pos] = l; 109 else 110 max_pos[pos] = 0; 111 return; 112 } 113 int mid = (l + r) >> 1; 114 if (x <= mid) 115 update(l,mid,pos<<1,x,val); 116 else 117 update(mid+1,r,pos<<1|1,x,val); 118 if (seg[pos<<1] >= seg[pos<<1|1]) 119 { 120 seg[pos] = seg[pos<<1]; 121 max_pos[pos] = max_pos[pos<<1]; 122 } 123 else 124 { 125 seg[pos] = seg[pos<<1|1]; 126 max_pos[pos] = max_pos[pos<<1|1]; 127 } 128 } 129 int ans[maxn]; 130 void solve() 131 { 132 for (int i = 1; i <= n; i++) 133 { 134 for (unsigned int j = 0; j < vec[i].size(); j++) 135 { 136 if (vec[i][j] > 0) 137 update(1,maxn,1,vec[i][j],1); 138 else 139 update(1,maxn,1,-vec[i][j],-1); 140 } 141 ans[fp[i]] = max_pos[1]; 142 } 143 for (int i = 1; i <= n; i++) 144 printf("%d ",ans[i]); 145 146 } 147 int main(void) 148 { 149 #ifndef ONLINE_JUDGE 150 freopen("in.txt","r",stdin); 151 #endif 152 while (~scanf ("%d%d",&n,&m)) 153 { 154 if ((n == 0) && (m == 0)) 155 break; 156 init(); 157 solve(); 158 } 159 return 0; 160 }