首页 > ACM题库 > HDU-杭电 > hdu 3601 A pungent problem待解决[解题报告]C++
2014
11-27

hdu 3601 A pungent problem待解决[解题报告]C++

A pungent problem

问题描述 :

One day, a couple of friends J and F were playing the game called “RiskCraft”. But J was so confused by what F told him that F almost wanted to bully him. At that time, the occurrence of cheat had exactly prevented J from being mistreated any longer.
Now it’s the time for F to make the strategy. There are several forts on the map, and each of the two forts has only one route to connect them. What’s more, F had been doing something quiet beyond the expectation. He just got each of the forts armed with a large amount of soldiers. But it seemed apparently that F knew J was cheating. So, F determined to alter the proportion of the army. J was definitely getting really misleading By F’s distorted strategies. So, he was really anxious of seeking the help of you.
Please number the forts from 1 to n. For instance, the fort ith number of solider is w(i) ( ps. w(i) may be a negative number as F likes. How rediculous!!), there are several tips of instructions that J hope s could help you work out this dilemma problem.
1. CHANGE u t: this means that F has the intention that he really want to change present group of the soldiers in fort u to t.
2. QMAX    u v : this actually indicates that J is curious about what is the max number of the soldiers of a certain forts on the way from u to v.
3. QSUM    u v : this absolutely expressed that J furiously have the temptation to know the whole number of the army from fort u to fort v.

输入:

There are several test cases.
In each test case, the first line is a positive integer n (1 <=n<=30000) means the number of fort.
The next n-1 lines include two numbers a, b (1<=a, b<=n) indicating there is a path between fort a and fort b.
The next line has n numbers, the i th number w(i) (-30000<=w(i)<=30000) means the amount of the army in fort i.
The following lines has a unique number q (0<=q<=200000), means the total operations in this test case.
Above all, q lines will be definitely displayed on screen, each line offers a string like ‘CHANGE u t’, ‘QMAX u v’ or ‘QSUM u v’.

输出:

There are several test cases.
In each test case, the first line is a positive integer n (1 <=n<=30000) means the number of fort.
The next n-1 lines include two numbers a, b (1<=a, b<=n) indicating there is a path between fort a and fort b.
The next line has n numbers, the i th number w(i) (-30000<=w(i)<=30000) means the amount of the army in fort i.
The following lines has a unique number q (0<=q<=200000), means the total operations in this test case.
Above all, q lines will be definitely displayed on screen, each line offers a string like ‘CHANGE u t’, ‘QMAX u v’ or ‘QSUM u v’.

样例输入:

4
1 2
2 3
4 1
4 2 1 3
12 
QMAX 3 4 
QMAX 3 3
QMAX 3 2
QMAX 2 3
QSUM 3 4
QSUM 2 1
CHANGE 1 5
QMAX 3 4
CHANGE 3 6
QMAX 3 4
QMAX 2 4
QSUM 3 4

样例输出:

4
1
2
2
10
6
5
6
5
16

Hint
The existence of the lines is impossible to be found between each test case.


  1. Good task for the group. Hold it up for every yeara??s winner. This is a excellent oppotunity for a lot more enhancement. Indeed, obtaining far better and much better is constantly the crucial. Just like my pal suggests on the truth about ab muscles, he just keeps obtaining much better.

  2. 其实国内大部分公司对算法都不够重视。特别是中小型公司老板根本都不懂技术,也不懂什么是算法,从而也不要求程序员懂什么算法,做程序从来不考虑性能问题,只要页面能显示出来就是好程序,这是国内的现状,很无奈。